Na esteira Eu publico problemas da trilha Algoritmo (programação esportiva clássica. Em uma hora e meia você precisa resolver três problemas em Java, C#, C++ ou Python.)
1. Torta para seis
Formulação do problema
O limite de tempo é de 4 segundos.
Você tem uma torta. 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ê deseja dividir a torta em seis pedaços de áreas iguais (mas não necessariamente do mesmo formato). Claro, qualquer um pode fazer isso em cinco cortes, mas só um profissional pode fazer isso em três cortes.
Encontre três cortes retos em um ponto que dividirão a torta em seis partes iguais. Imprima {x, y, d1, d2, d3}, onde (x, y) é o ponto comum de todos os três cortes e d1, d2, d3 são os ângulos de direção dos cortes em radianos.
DefiniçãoClasse: CakeForSix
Método:cortar
Parâmetros: int[], int[] Retorna: double[] Assinatura do método: double[] cut(int[] x, int[] y)
(certifique-se de que seu método seja 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 inteiro k.
- Você pode gerar qualquer direção, elas não precisam ser de [0, pi).
- O avaliador calculará a área dos seus seis pedaços de bolo em dobro. A resposta será aceita se a diferença relativa ou absoluta entre elas for menor que 10^(-4).
- Mais precisamente, seja X e Y a menor e a maior das seis áreas calculadas pelo avaliador. Então sua resposta será aceita se Y
- (A versão original do problema usava uma precisão de 1e-7 em vez de 1e-4. Para resolver este problema no arquivo, o limite de precisão foi reduzido devido à presença de casos de chamada que provavelmente tornariam o problema insolúvel com precisão de 1e-7. Em um mundo ideal, os limites não permitem tais casos e ainda exigem alta precisão, portanto, resolver o problema com alguma otimização numérica geral não é fácil.)
Restrições
- x contém de 3 a 50 elementos inclusive.
- y contém o mesmo número de elementos que x.
- todas as coordenadas entre 0 e 10 inclusive
- x e y definem um polígono convexo no sentido anti-horário.
Original em inglês
Problema Declaração
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 em int[]sx e y.
Você tem cinco amigos. Agora você deseja cortar o bolo em seis pedaços de áreas iguais (mas não necessariamente de formato igual). Claro, qualquer um pode fazer isso em cinco cortes – mas apenas um verdadeiro profissional pode fazer isso em três!
Encontre três cortes retos passando pelo mesmo ponto que cortou o bolo em seis partes igualmente grandes. 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:cortar
Parâmetros: int[], int[] Retorna: double[] Assinatura do método: double[] cut(int[] x, int[] y)
(certifique-se de que seu método seja 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 é igual a um corte na direção pi*k+d para qualquer número inteiro k.
— Você pode retornar quaisquer direções, elas não precisam ser de [0,pi).
— O avaliador calculará as áreas dos seus seis pedaços de bolo em dobro. A resposta será aceita se a diferença relativa ou absoluta entre elas for menor que 10^(-4).
— Mais precisamente, sejam X e Y a menor e a maior das suas seis áreas, conforme computado pelo avaliador. Então, sua resposta será aceita se Y < max( X + 10^(-4), X * (1+10^(-4)) ).
— (A versão original do problema usava precisão 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 de desafio que provavelmente tornam a tarefa insolúvel com precisão 1e-7 Num mundo ideal, as restrições não permitiriam tais casos e ainda exigiriam alta precisão, de modo que não seria fácil resolver o problema através 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 no sentido anti-horário.
Примеры
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
retorna:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787}
Um hexágono simétrico, mas irregular. A resposta do exemplo corresponde a cortá-lo ao meio na horizontal e fazer outros dois cortes no centro que dividem cada pedaço em três pedaços.
1)
{0, 1000, 0}
{0, 0, 1000}
retorna:
{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}
retorna:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475}
Pentágono irregular.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Retorna: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705}
Um quadrado girou 45 graus.
[]
Apenas usuários registrados podem participar da pesquisa. por favor
Eu resolvi o problema para
-
em menos de 10 minutos
-
10 30 minutos-
-
30 60 minutos-
-
1 2-horas
-
em mais de 2 horas
-
outro
42 usuários votaram. 47 usuários se abstiveram.
Fonte: habr.com