🥇Problema de la TopCoder Open 2019: tăiem prăjitura în șase părți

Problema de la TopCoder Open 2019: tăiem un tort în șase părți
Pe urmele „Echipa noastră a câștigat: TopCoder Open 2019” public probleme din cadrul traseului Algoritm (programare competitivă clasică. Într-o oră și jumătate trebuie să rezolvi trei probleme în Java, C#, C++ sau Python.)

1. Tortul pentru șase

Formularea problemei

Limita de timp – 4 secunde.

Aveți un tort. Privind din sus, tortul are forma unui poligon (strict) convex. Vi se dau coordonatele vârfurilor în numere întregi X și Y.

Aveți cinci prieteni. Doriți să împărțiți tortul în șase părți de aceeași suprafață (dar nu neapărat de aceeași formă). Desigur, oricine poate face acest lucru în cinci tăieturi, dar doar un profesionist poate face asta în trei tăieturi.

Găsiți trei tăieturi cu linii drepte printr-un singur punct, care împart tortul în șase părți de aceeași suprafață. Returnați {x, y, d1, d2, d3}, unde (x, y) este punctul comun al celor trei tăieturi, iar d1, d2, d3 sunt unghiurile de direcție ale tăieturilor în radiani.

DefinițieClasă: CakeForSix
Metodă: cut
Parametrii: int[], int[]
Returnează: double[]
Semnătura metodei: double[] cut(int[] x, int[] y)
(asigurați-vă că metodologia dvs. este publică)

Note

Direcția pozitivă pe axa x este 0 (radiani), iar direcția pozitivă pe axa y este pi/2 (radiani).
Tăietura în direcția d este similară cu tăietura în direcția pi*k+d pentru orice număr întreg k.
Puteți returna orice direcții, acestea nu trebuie neapărat să fie din intervalul [0, pi).
Graderul va calcula suprafețele celor șase bucăți de tort în doubles. Răspunsul va fi acceptat dacă diferența relativă sau absolută între acestea este mai mică de 10^(-4).
Mai exact, să presupunem că X și Y sunt cele mai mici și cele mai mari dintre cele șase arii calculate de grader. Atunci răspunsul dvs. va fi acceptat dacă Y < max(X+10^(-4), X*1+10^(-4))).
(În versiunea inițială a problemei s-a folosit o precizie de 1e-7 în loc de 1e-4. Pentru a rezolva această problemă, în arhivă limita de precizie a fost redusă din cauza cazurilor de apel care ar face probabil problema imposibil de rezolvat cu o precizie de 1e-7. Într-o lume ideală, constrângerile nu ar permite astfel de cazuri și ar solicita încă o precizie ridicată, așa că rezolvarea problemei printr-o optimizare numerică comună nu este ușoară.)

Limitări

x conține între 3 și 50 de elemente inclusiv.
y conține același număr de elemente ca și x.
toate coordonatele sunt între 0 și 10 000 inclusiv
x și y definesc un poligon convex în direcția inversă acelor de ceasornic.

Originalul în engleză

Declarația problemei

Limita de timp este de 4 secunde.

Ai o prăjitură. Văzută dintr-o parte, prăjitura este un polygon (strict) convexe. Ți se dau coordonatele vârfurilor în array-urile int[] x și y.

Ai cinci prieteni. Acum vrei să tai prăjitura în șase piese de suprafață egală (dar nu neapărat de formă egală). Desigur, oricine poate face asta în cinci tăieturi — dar doar un adevărat profesionist poate face asta în trei!

Găsește trei tăieturi liniare care trec prin același punct și care taie prăjitura în șase părți egale. Returnează {x, y, d1, d2, d3}, unde (x, y) este punctul comun al celor trei tăieturi, iar d1, d2, d3 sunt direcțiile lor în radiani.

Definiție

Clasă: CakeForSix
Metodă: cut
Parametrii: int[], int[]
Returnează: double[]
Semnătura metodei: double[] cut(int[] x, int[] y)
(asigurați-vă că metodologia dvs. este publică)

Note
— Direcția pozitivă pe axa x este 0 (radiani), direcția pozitivă pe axa y este pi/2 (radiani).
— O tăietură în direcția d este aceeași cu o tăietură în direcția pi*k+d pentru orice integer k.
— Poți returna orice direcții, nu trebuie să fie din [0, pi).
— Corectorul va calcula ariile celor șase piese de prăjitură în double. Răspunsul va fi acceptat dacă diferența relativă sau absolută între ele este mai mică decât 10^(-4).
— Mai precis, să lăsăm X și Y să fie cel mai mic și cel mai mare dintre cele șase ariile tale, așa cum sunt calculate de corector. Atunci, răspunsul tău va fi acceptat dacă Y < max(X + 10^(-4), X * (1+10^(-4))).
— (Versiunea originală a problemei a folosit precizia de 1e-7 în loc de 1e-4. Pentru a rezolva această problemă în arhivă, limita de precizie a fost scăzută din cauza existenței cazurilor dificile care cel mai probabil fac sarcina nerezolvabilă cu 1e-7 precizie. Într-o lume ideală, constrângerile nu ar permite astfel de cazuri și totuși ar necesita o precizie ridicată, astfel încât să nu fie ușor să se rezolve problema printr-o optimizare numerică generală.)

Condiții
— x va avea între 3 și 50 de elemente, inclusiv.
— y va avea același număr de elemente ca și x.
— Toate coordonatele vor fi între 0 și 10.000, inclusiv.
— x și y vor descrie un polygon convex în ordinea contraclockwise.

Exemple

{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Returnează:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }

Un hexagon simetric, dar nu regulat. Exemplul de răspuns corespunde tăierii lui pe jumătate pe orizontală și efectuării a două alte tăieturi pe centru, care împart fiecare parte în trei părți.

Problema de la TopCoder Open 2019: tăiem un tort în șase părți

1)

{0, 1000, 0}
{0, 0, 1000}
Returnează:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }

Un triunghi dreptunghi. Din nou, putem începe cu una dintre cele trei tăieturi de-a lungul axei de simetrie.

Problema de la TopCoder Open 2019: tăiem un tort în șase părți

2)

{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Returnează:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }

Un pentagon neregulat.

Problema de la TopCoder Open 2019: tăiem un tort în șase părți

3)