{"id":163,"date":"2017-03-13T14:45:09","date_gmt":"2017-03-13T17:45:09","guid":{"rendered":"http:\/\/www.galirows.com.br\/meublog\/competir\/?p=163"},"modified":"2017-03-16T09:38:48","modified_gmt":"2017-03-16T12:38:48","slug":"elevador-maratona2010","status":"publish","type":"post","link":"https:\/\/www.galirows.com.br\/meublog\/competir\/elevador-maratona2010\/","title":{"rendered":"Elevador [Maratona 2010]"},"content":{"rendered":"
\n

A FCC (F\u00e1brica de Cilindros de Carbono) fabrica v\u00e1rios tipos de cilindros de carbono. A FCC est\u00e1 instalada no d\u00e9cimo andar de um pr\u00e9dio, e utiliza os v\u00e1rios elevadores do pr\u00e9dio para transportar os cilindros. Por quest\u00e3o de seguran\u00e7a, os cilindros devem ser transportados na posi\u00e7\u00e3o vertical; como s\u00e3o pesados, no m\u00e1ximo dois cilindros podem ser transportados em uma \u00fanica viagem de elevador. Os elevadores t\u00eam formato de paralelep\u00edpedo e sempre t\u00eam altura maior que a altura dos cilindros.<\/p>\n

Para minimizar o n\u00famero de viagens de elevador para transportar os cilindros, a FCC quer, sempre que poss\u00edvel, colocar dois cilindros no elevador. A figura abaixo ilustra, esquematicamente (vista superior), um caso em que isto \u00e9 poss\u00edvel (a), e um caso em que isto n\u00e3o \u00e9 poss\u00edvel (b):<\/p>\n

\"\"<\/a><\/p>\n

Como existe uma quantidade muito grande de elevadores e de tipos de cilindros, a FCC quer que voc\u00ea escreva um programa que, dadas as dimens\u00f5es do elevador e dos dois cilindros, determine se \u00e9 poss\u00edvel colocar os dois cilindros no elevador.<\/p>\n<\/div>\n

<\/p>\n

Entrada<\/strong><\/p>\n

\n

A entrada cont\u00e9m v\u00e1rios casos de teste. A primeira e \u00fanica linha de cada caso de teste cont\u00e9m quatro n\u00fameros inteiros L<\/strong>, C<\/strong>, R1<\/strong> e R2<\/strong>, separados por espa\u00e7os em branco, indicando respectivamente a largura do elevador (1 \u2264 L<\/strong> \u2264 100), o comprimento do elevador (1 \u2264 C<\/strong> \u2264 100), e os raios dos cilindros (1 \u2264 R1<\/strong>, R2<\/strong> \u2264 100).<\/p>\n

O \u00faltimo caso de teste \u00e9 seguido por uma linha que cont\u00e9m quatro zeros separados por espa\u00e7os em branco.<\/p>\n<\/div>\n

Sa\u00edda<\/strong><\/p>\n

\n

Para cada caso de teste, o seu programa deve imprimir uma \u00fanica linha com um \u00fanico caractere: \u2018S\u2019 se for poss\u00edvel colocar os dois cilindros no elevador e \u2018N\u2019 caso contr\u00e1rio.<\/p>\n

<\/div>\n\n\n\n\n\n
Exemplo de Entrada<\/td>\nExemplo de Sa\u00edda<\/td>\n<\/tr>\n<\/thead>\n
11 9 2 3
\n7 8 3 2
\n10 15 3 7
\n8 9 3 2
\n0 0 0 0<\/td>\n		S
\nN
\nN
\nS<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Dica<\/strong><\/p>\n

Podemos resolver diretamente alguns casos com uma verifica\u00e7\u00e3o inicial simples: a menor dimens\u00e3o da caixa, seja ela a largura ou a altura, deve ser suficientemente grande para que a circunfer\u00eancia de maior di\u00e2metro<\/b> possa ser colocada l\u00e1.<\/p>\n

Devemos agora colocar as duas circunfer\u00eancias lado a lado, de modo que elas se tangenciam e tangenciam uma mesma aresta do ret\u00e2ngulo dado. \u00c9 nesta posi\u00e7\u00e3o que elas ocupam o menor espa\u00e7o poss\u00edvel, e a dist\u00e2ncia entre os centros \u00e9 m\u00ednima. Seja R<\/span><\/span><\/span><\/span> o segmento que liga os centros das circunfer\u00eancias (R<\/span>=<\/span>R<\/span>1<\/span>+<\/span>R<\/span>2<\/span><\/span><\/span><\/span>). \u00c9 f\u00e1cil perceber que conseguimos construir um trap\u00e9zio ligando os centros das circunfer\u00eancias \u00e0 aresta que foi tangenciada. Desse trap\u00e9zio, extra\u00edmos um tri\u00e2ngulo ret\u00e2ngulo cuja hipotenusa \u00e9 justamente R<\/span><\/span><\/span><\/span>.<\/p>\n

Agora, podemos afastar as duas circunfer\u00eancias o m\u00e1ximo poss\u00edvel, colocando-as em extremidades diagonalmente opostas da caixa. Conseguimos construir um segundo trap\u00e9zio ligando os centros a uma mesma aresta, e dele extrair um segundo tri\u00e2ngulo ret\u00e2ngulo de hipotenusa R<\/span>\u2032<\/span><\/span><\/span><\/span><\/span>. O comprimento de R<\/span>\u2032<\/span><\/span><\/span><\/span><\/span> \u00e9 a dist\u00e2ncia m\u00e1xima, dentro da caixa, entre os centros das circunfer\u00eancias.<\/p>\n

Se R<\/span>\u2032<\/span><\/span>><\/span>R<\/span><\/span><\/span><\/span>, os c\u00edrculos cabem na caixa, e respondemos S<\/b>. Se R<\/span>\u2032<\/span><\/span><<\/span>R<\/span><\/span><\/span><\/span>, temos que na situa\u00e7\u00e3o de afastamento m\u00e1ximo existe uma interse\u00e7\u00e3o entre os c\u00edrculos , ou seja, os c\u00edrculos n\u00e3o cabem na caixa. Assim, respondemos N<\/b>.<\/p>\n

Dica retirada de: http:\/\/wiki.maratona.dcc.ufmg.br\/index.php\/ELEVADOR<\/a><\/em><\/p>\n

Solu\u00e7\u00e3o em C<\/strong><\/p>\n

#include <stdio.h>\r\n#include <math.h>\r\n\r\nint main() {\r\n\tint l, c, r1, r2, maior;\r\n\tchar saida;\r\n\t\r\n\twhile ( scanf(\"%i %i %i %i\",&l, &c, &r1, &r2) ) {\r\n\t\tif(l == 0 && c == 0 && r1 == 0 && r2 == 0) { return 0; }\r\n\t\t\/\/o teste poderia ser: l+c+r1+r2 == 0\r\n\t\t\/\/como os numeros sao sempre positivos, nao teria problema\r\n\t\t\r\n\t\tsaida = 'N';\r\n\t\tif (r1 > r2) {\r\n\t\t\tmaior = r1 + r1;\r\n\t\t} else {\r\n\t\t\tmaior = r2 + r2;\r\n\t\t}\r\n\t\r\n\t\tif(maior <= l && maior <= c) {\r\n\t\t\tif(sqrt(pow((l - r2 - r1), 2) + pow((c - r2 - r1), 2)) >=  r1 + r2) {\r\n\t\t\t\tsaida = 'S';\r\n\t\t\t}\r\n\t\t}\r\n\t\t\r\n\t\tprintf(\"%c\\n\",saida);\t\r\n\t}\t\r\n\treturn 0;\r\n}<\/pre>\n<\/div>\n
Teste o c\u00f3digo:<\/strong> http:\/\/ideone.com\/MW0fbR<\/a><\/p>\n
 <\/p>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
A FCC (F\u00e1brica de Cilindros de Carbono) fabrica v\u00e1rios tipos de cilindros de carbono. A FCC est\u00e1 instalada no d\u00e9cimo andar de um pr\u00e9dio, e utiliza os v\u00e1rios elevadores do pr\u00e9dio para transportar os cilindros. Por quest\u00e3o de seguran\u00e7a, os cilindros devem ser transportados na posi\u00e7\u00e3o vertical; como s\u00e3o pesados, no m\u00e1ximo dois cilindros podem […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8,7],"tags":[13],"class_list":["post-163","post","type-post","status-publish","format-standard","hentry","category-cc","category-maratona-de-programacao","tag-geometria-computacional"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t