Aos pasos Publico problemas desde a pista Algoritmo (programación deportiva clásica. En hora e media precisas resolver tres problemas en Java, C#, C++ ou Python).
1. Empanada para seis
Declaración de problemas
O límite de tempo é de 4 segundos.
Tes unha empanada. Visto desde arriba, o bolo ten a forma dun polígono (estrictamente) convexo. Dámosche as coordenadas dos vértices en números enteiros X e Y.
Tes cinco amigos. Quere dividir a torta en seis pezas de igual área (pero non necesariamente a mesma forma). Por suposto, calquera pode facelo en cinco cortes, pero só un profesional pode facelo en tres cortes.
Busca tres cortes en liña recta nun punto que dividirán a torta en seis partes iguais. Imprima {x, y, d1, d2, d3}, onde (x, y) é o punto común dos tres cortes, e d1, d2, d3 son os ángulos de dirección dos cortes en radians.
DefiniciónClase: CakeForSix
Método: corte
Parámetros: int[], int[] Devolve: double[] Sinatura do método: double[] cut(int[] x, int[] y)
(asegúrese de que o seu método sexa público)
Notas
- A dirección positiva ao longo do eixe x é 0 (radiáns), a dirección positiva ao longo do eixe y é pi/2 (radiáns).
- Un corte na dirección d é semellante a un corte na dirección pi*k+d para calquera número enteiro k.
- Podes emitir calquera dirección, non teñen que ser de [0, pi).
- O alumno calculará a área dos teus seis anacos de bolo en dobres. A resposta aceptarase se a diferenza relativa ou absoluta entre elas é inferior a 10^(-4).
- Máis precisamente, sexa X e Y as máis pequenas e maiores das túas seis áreas calculadas polo alumno. Entón a súa resposta será aceptada se Y
- (A versión orixinal do problema utilizaba unha precisión de 1e-7 en lugar de 1e-4. Para resolver este problema no arquivo, o límite de precisión reduciuse debido á presenza de casos de chamada que probablemente farían que o problema non fose resolto cunha precisión). de 1e-7. Nun mundo ideal, os límites non permiten tales casos e aínda requiren alta precisión, polo que resolver o problema con algunha optimización numérica xeral non é doado.)
Restricións
- x contén de 3 a 50 elementos incluídos.
- y contén o mesmo número de elementos que x.
- todas as coordenadas entre 0 e 10 inclusive
- x e y definen un polígono convexo en sentido antihorario.
Orixinal en inglés
Declaración do problema
O límite de tempo é de 4 segundos.
Tes unha torta. Visto desde arriba, o bolo é un polígono (estrictamente) convexo. Dámosche as coordenadas dos seus vértices nos int[]sx e y.
Tes cinco amigos. Agora queres cortar o bolo en seis anacos de igual área (pero non necesariamente a mesma forma). Por suposto, calquera pode facelo en cinco cortes, pero só un verdadeiro profesional pode facelo en tres!
Busca tres cortes en liña recta que pasen polo mesmo punto que cortaron o bolo en seis partes igualmente grandes. Retorna {x, y, d1, d2, d3}, onde (x, y) é o punto común dos tres cortes e d1, d2, d3 son as súas direccións en radiáns.
Definición
Clase: CakeForSix
Método: corte
Parámetros: int[], int[] Devolve: double[] Sinatura do método: double[] cut(int[] x, int[] y)
(asegúrese de que o seu método sexa público)
Notas
— A dirección positiva ao longo do eixe x é 0 (radiáns), a dirección positiva ao longo do eixe y é pi/2 (radiáns).
— Un corte na dirección d é o mesmo que un corte na dirección pi*k+d para calquera número enteiro k.
— Podes devolver as indicacións, non teñen que ser de [0,pi).
— O alumno calculará as áreas das súas seis pezas de bolo en dobres. A resposta aceptarase se a diferenza relativa ou absoluta entre elas é inferior a 10^(-4).
— Máis precisamente, sexa X e Y as máis pequenas e máis grandes das túas seis áreas, calculadas polo alumno. Entón, a súa resposta será aceptada se Y < max( X + 10^(-4), X * (1+10^(-4)) ).
— (A versión orixinal do problema utilizaba a precisión 1e-7 en lugar de 1e-4. Para resolver este problema no arquivo, o límite de precisión reduciuse debido á existencia de casos de desafío que moi probablemente fan que a tarefa non se resolva con precisión 1e-7. Nun mundo ideal, as restricións non permitirían tales casos e aínda requiren alta precisión, polo que non é fácil resolver o problema mediante algunha optimización numérica xeral.)
Restriccións
— x terá entre 3 e 50 elementos, incluídos.
— y terá o mesmo número de elementos que x.
— Todas as coordenadas estarán entre 0 e 10,000, inclusive.
— x e y describirán un polígono convexo en sentido antihorario.
Exemplos
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Devolucións:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Un hexágono simétrico pero irregular. O exemplo de resposta corresponde a cortalo pola metade horizontalmente e facer outros dous cortes polo centro que dividen cada peza en tres anacos.
1)
{0, 1000, 0}
{0, 0, 1000}
Devolucións:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Triángulo rectángulo. De novo, podemos comezar cun dos tres cortes ao longo do eixe de simetría.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Devolucións:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Pentágono irregular.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Devolucións: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Un cadrado xiraba 45 graos.
[]
Só os usuarios rexistrados poden participar na enquisa. , por favor.
Resolvín o problema para
-
en menos de 10 minutos
-
minutos 10-30
-
minutos 30-60
-
1-2 horas
-
en máis de 2 horas
-
outro
Votaron 42 usuarios. 47 usuarios abstivéronse.
Fonte: www.habr.com