🥇Desafío TopCoder Open 2019: Cortar unha torta en seis anacos

Desafío TopCoder Open 2019: corta a torta en seis anacos
Aos pasos "O noso equipo gañou: TopCoder Open 2019" Estou a publicar problemas da sección de Algoritmos. (Programación competitiva clásica. Debes resolver tres problemas en Java, C#, C++ ou Python nunha hora e media.)

1. Empanada para seis

Declaración de problemas

Límite de tempo: 4 segundos.

Tes unha torta. Vista desde arriba, a torta ten a forma dun polígono (estritamente) convexo. Dámosche as coordenadas enteiras dos vértices, X e Y.

Tes cinco amigos. Queres dividir unha torta en seis anacos iguais (pero non necesariamente da mesma forma). Claro, calquera pode facelo en cinco cortes, pero só un profesional pode facelo en tres.

Atopa tres cortes con liñas rectas a través dun punto común que dividan a torta en seis partes de igual área. Imprime {x, y, d1, d2, d3}, onde (x, y) é o punto común dos tres cortes e d1, d2, d3 son os ángulos dos cortes en radiáns.

DefiniciónClase: CakeForSix
Método: corte
Parámetros: int[], int[]
Retorna: double[]
Sinatura do método: double[] cut(int[] x, int[] y)
(asegúrate de que o teu 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).
O corte na dirección d é análogo ao corte na dirección pi*k+d para calquera enteiro k.
Podes mostrar calquera dirección, non ten que ser desde [0, pi).
O avaliador calculará as áreas das túas seis porcións de bolo por dobre. A resposta aceptarase se a diferenza relativa ou absoluta entre elas é menor que 10^(-4).
Máis precisamente, sexan X e Y a menor e a maior das seis áreas calculadas polo cualificador. Entón, a túa resposta aceptarase se Y
(A versión orixinal do problema empregaba unha precisión de 1e-7 en lugar de 1e-4. Para solucionar este problema, o límite de precisión reduciuse no arquivo debido á presenza de casos de chamada que probablemente fan que o problema sexa intratable cunha precisión de 1e-7. Nun mundo ideal, as restricións impiden tales casos e aínda requiren unha alta precisión, polo que resolver o problema con algunha optimización numérica xeral non é sinxelo.)

Restricións

x contén de 3 a 50 elementos, ambos incluídos.
y contén o mesmo número de elementos que x.
todas as coordenadas entre 0 e 10.000 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 un pastel. Visto desde arriba, o pastel é un polígono (estritamente) convexo. Dánseche as coordenadas dos seus vértices nos intervalos int[]sx e y.

Tes cinco amigos. Agora queres cortar o pastel en seis anacos de igual superficie (pero non necesariamente da mesma forma). Por suposto, calquera pode facelo en cinco cortes, pero só un verdadeiro profesional pode facelo en tres!

Atopa tres cortes en liña recta que pasen polo mesmo punto e que corten o pastel en seis partes igualmente grandes. Devolve {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[]
Retorna: double[]
Sinatura do método: double[] cut(int[] x, int[] y)
(asegúrate de que o teu 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 enteiro k.
— Podes devolver calquera dirección, non teñen que ser desde [0,pi).
— O avaliador calculará as áreas dos teus seis anacos de bolo por dobres. A resposta aceptarase se a diferenza relativa ou absoluta entre eles é menor que 10^(-4).
— Máis precisamente, sexan X e Y a menor e a maior das túas seis áreas, segundo as calculadas polo cualificador. Entón, a túa resposta aceptarase se Y < max( X + 10^(-4), X * (1+10^(-4)) ).
— (A versión orixinal do problema empregaba 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 á existencia de casos de desafío que moi probablemente fan que a tarefa sexa irresoluble cunha precisión de 1e-7. Nun mundo ideal, as restricións non permitirían tales casos e aínda así requirirían unha alta precisión, polo que non é doado resolver o problema mediante algunha optimización numérica xeral.)

Restriccións
— x terá entre 3 e 50 elementos, ambos incluídos.
— y terá o mesmo número de elementos que x.
— Todas as coordenadas estarán entre 0 e 10,000, ambos incluídos.
— x e y describirán un polígono convexo en orde antihoraria.

Exemplos

{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. A resposta de exemplo corresponde a cortalo pola metade horizontalmente e facer outros dous cortes polo centro, dividindo cada metade en tres.

Desafío TopCoder Open 2019: corta a torta en seis 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.

Desafío TopCoder Open 2019: corta a torta en seis anacos

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.

Desafío TopCoder Open 2019: corta a torta en seis anacos

3)