Seguindo as trilhas publicando problemas da trilha Algorithm (programação competitiva clássica. Em uma hora e meia, é necessário resolver três problemas em Java, C#, C++ ou Python.)
1. Bolo para seis
Formulação do problema
Limite de tempo — 4 segundos.
Você tem um bolo. Quando visto de cima, o bolo tem a forma de um polígono (estritamente) convexo. Você recebe as coordenadas dos vértices em números inteiros X e Y.
Você tem cinco amigos. Você quer dividir o bolo em seis partes de área igual (mas não necessariamente de forma igual). Claro, qualquer um pode fazer isso em cinco cortes, mas apenas um profissional pode fazer isso em três cortes.
Encontre três cortes em linhas retas através de um ponto que dividirão o bolo em seis partes de área igual. Saída {x, y, d1, d2, d3}, onde (x, y) é o ponto comum dos três cortes e d1, d2, d3 são os ângulos de direção dos cortes em radianos.
DefiniçãoClasse: CakeForSix
Método: cut
Parâmetros: int[], int[]
Retorna: double[]
Assinatura do método: double[] cut(int[] x, int[] y)
(certifique-se de que seu método é público)
Notas
- A direção positiva ao longo do eixo x é 0 (radianos), a direção positiva ao longo do eixo y é pi/2 (radianos).
- Um corte na direção d é semelhante a um corte na direção pi*k+d para qualquer número inteiro k.
- Você pode devolver quaisquer direções, não precisam necessariamente estar em [0, pi).
- O avaliador calculará as áreas de suas seis peças de bolo em doubles. A resposta será aceita se a diferença relativa ou absoluta entre elas for menor que 10^(-4).
- Mais precisamente, deixe X e Y serem as áreas mais pequenas e mais grandes das suas seis áreas, calculadas pelo avaliador. Então sua resposta será aceita se Y < max (X+10^(-4), X*1+10^(-4))).
- (Na versão original do problema, foi usada uma precisão de 1e-7 em vez de 1e-4. Para resolver esse problema, no arquivo, o limite de precisão foi reduzido devido à existência de casos que provavelmente fazem o problema irremediável com precisão de 1e-7. Em um mundo ideal, as restrições não deveriam permitir tais casos e ainda exigir alta precisão, então resolver o problema com alguma otimização numérica generalizada não é fácil.)
Restrições
- x contém de 3 a 50 elementos inclusivos.
- y contém o mesmo número de elementos que x.
- todas as coordenadas entre 0 e 10 000 inclusivas
- x e y descrevem um polígono convexo na direção anti-horária.
Original em inglês
Declaração do Problema
O limite de tempo é de 4 segundos.
Você tem um bolo. Visto de cima, o bolo é um polígono (estritamente) convexo. Você recebe as coordenadas de seus vértices nos int[]s x e y.
Você tem cinco amigos. Agora você quer cortar o bolo em seis pedaços de área igual (mas não necessariamente de formato igual). Claro, qualquer um pode fazer isso em cinco cortes — mas apenas um verdadeiro profissional pode fazer em três!
Encontre três cortes em linha reta que passem pelo mesmo ponto e cortem o bolo em seis partes iguais. Retorne {x, y, d1, d2, d3}, onde (x, y) é o ponto comum dos três cortes, e d1, d2, d3 são suas direções em radianos.
Definição
Classe: CakeForSix
Método: cut
Parâmetros: int[], int[]
Retorna: double[]
Assinatura do método: double[] cut(int[] x, int[] y)
(certifique-se de que seu método é público)
Notas
— A direção positiva ao longo do eixo x é 0 (radianos), a direção positiva ao longo do eixo y é pi/2 (radianos).
— Um corte na direção d é o mesmo que um corte na direção pi*k+d para qualquer inteiro k.
— Você pode retornar quaisquer direções, não precisam ser de [0, pi).
— O corretor calculará as áreas dos seus seis pedaços de bolo em doubles. A resposta será aceita se a diferença relativa ou absoluta entre elas for menor que 10^(-4).
— Mais precisamente, deixe X e Y serem o menor e o maior de suas seis áreas, conforme calculado pelo corretor. Então, sua resposta será aceita se Y < max(X + 10^(-4), X * (1 + 10^(-4))).
— (A versão original do problema usou precisão de 1e-7 em vez de 1e-4. Para resolver este problema no arquivo, o limite de precisão foi reduzido devido à existência de casos desafiadores que provavelmente tornam a tarefa não solucionável com 1e-7 de precisão. Em um mundo ideal, as restrições não permitiriam tais casos e ainda exigiriam alta precisão, de modo que não fosse fácil resolver o problema por meio de alguma otimização numérica geral.)
Restrições
— x terá entre 3 e 50 elementos, inclusive.
— y terá o mesmo número de elementos que x.
— Todas as coordenadas estarão entre 0 e 10.000, inclusive.
— x e y descreverão um polígono convexo em ordem anti-horária.
Exemplos
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Retornos:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Hexágono simétrico, mas não regular. Um exemplo de resposta corresponde a cortá-lo ao meio horizontalmente e a realização de outros dois cortes pelo centro, que dividem cada parte em três partes.
1)
{0, 1000, 0}
{0, 0, 1000}
Retornos:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Triângulo retângulo. Novamente, podemos começar com um dos três cortes ao longo do eixo de simetria.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Retornos:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Pentágono irregular.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Retornos: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Quadrado rotacionado em 45 graus.
[]
Apenas usuários registrados podem participar da pesquisa. , por favor.
Resolvi o problema em
menos de 10 minutos
10-30 minutos
30-60 minutos
1-2 horas
mais de 2 horas
outro
42 usuários votaram. 47 usuários se abstiveram.
Fonte: habr.com
