Pe urme Public probleme din pista Algoritm (programare sportivă clasică. Într-o oră și jumătate trebuie să rezolvi trei probleme în Java, C#, C++ sau Python.)
1. Plăcintă pentru șase
Declarație de problemă
Limita de timp este de 4 secunde.
Ai o plăcintă. Privită de sus, prăjitura are forma unui poligon (strict) convex. Vi se dau coordonatele vârfurilor în numere întregi X și Y.
Ai cinci prieteni. Vrei să împărțiți plăcinta în șase bucăți de suprafață egală (dar nu neapărat aceeași formă). Desigur, oricine o poate face în cinci tăieturi, dar numai un profesionist o poate face în trei tăieturi.
Găsiți trei tăieturi în linii drepte printr-un punct care vor împărți plăcinta în șase părți egale. Tipăriți {x, y, d1, d2, d3}, unde (x, y) este punctul comun al tuturor celor trei tăieturi, iar d1, d2, d3 sunt unghiurile de direcție ale tăieturilor în radiani.
DefinițieClasa: CakeForSix
Metoda: taiere
Parametri: int[], int[] Returnează: double[] Semnătura metodei: double[] cut(int[] x, int[] y)
(asigură-te că metoda ta este publică)
Notițe
- Direcția pozitivă de-a lungul axei x este 0 (radiani), direcția pozitivă de-a lungul axei y este pi/2 (radiani).
- O tăietură în direcția d este similară cu o tăietură în direcția pi*k+d pentru orice număr întreg k.
- Puteți scoate orice direcție, nu trebuie să fie de la [0, pi).
- Evaluătorul va calcula suprafața celor șase bucăți de tort în dublu. Răspunsul va fi acceptat dacă diferența relativă sau absolută dintre ele este mai mică de 10^(-4).
- Mai precis, să fie X și Y cele mai mici și mai mari dintre cele șase suprafețe calculate de către evaluator. Atunci răspunsul tău va fi acceptat dacă Y
- (Versiunea originală a problemei folosea 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 prezenței cazurilor de apelare care probabil ar face problema nerezolvată cu o precizie). din 1e-7. Într-o lume ideală, limitele nu permit astfel de cazuri și necesită totuși precizie ridicată, așa că rezolvarea problemei cu o optimizare numerică generală nu este ușoară.)
Restricții
- x conține de la 3 la 50 de elemente inclusiv.
- y conține același număr de elemente ca x.
- toate coordonatele între 0 și 10 inclusiv
- x și y definesc un poligon convex în sens invers acelor de ceasornic.
original in engleza
Declarație problemă
Limita de timp este de 4 de secunde.
Ai un tort. Privită de sus, prăjitura este un poligon (strict) convex. Vi se dau coordonatele vârfurilor sale în int[]sx și y.
Ai cinci prieteni. Acum doriți să tăiați tortul în șase bucăți de suprafață egală (dar nu neapărat formă egală). Desigur, oricine poate face asta în cinci tăieturi, dar numai un profesionist adevărat poate face asta în trei!
Găsiți trei tăieturi drepte care trec prin același punct și care au tăiat tortul în șase părți la fel de mari. 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
Clasa: CakeForSix
Metoda: taiere
Parametri: int[], int[] Returnează: double[] Semnătura metodei: double[] cut(int[] x, int[] y)
(asigură-te că metoda ta este publică)
notițe
— Direcția pozitivă de-a lungul axei x este 0 (radiani), direcția pozitivă de-a lungul axei 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 număr întreg k.
— Puteți returna orice indicații, nu trebuie să fie de la [0,pi).
— Evaluatorul va calcula suprafețele celor șase bucăți de tort în dublu. Răspunsul va fi acceptat dacă diferența relativă sau absolută dintre ele este mai mică de 10^(-4).
— Mai precis, să fie X și Y cele mai mici și cele mai mari dintre cele șase zone ale tale, așa cum au fost calculate de către evaluator. Apoi, răspunsul tău va fi acceptat dacă Y < max( X + 10^(-4), X * (1+10^(-4)) ).
— (Versiunea originală a problemei folosea precizia 1e-7 în loc de 1e-4. Pentru rezolvarea acestei probleme în arhivă, limita de precizie a fost redusă din cauza existenței unor cazuri de provocare care, cel mai probabil, fac sarcina de nerezolvat cu precizie 1e-7 Într-o lume ideală, constrângerile nu ar permite astfel de cazuri și necesită totuși precizie ridicată, astfel încât nu este ușor să rezolvi problema printr-o optimizare numerică generală.)
Constrângerile
— x va avea între 3 și 50 de elemente, inclusiv.
— y va avea același număr de elemente ca x.
— Toate coordonatele vor fi cuprinse între 0 și 10,000, inclusiv.
— x și y vor descrie un poligon convex în sens invers acelor de ceasornic.
exemple
0)
{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 neregulat. Exemplul de răspuns corespunde tăierii lui în jumătate pe orizontală și efectuarea altor două tăieturi în centru care împart fiecare bucată în trei părți.
1)
{0, 1000, 0}
{0, 0, 1000}
Returnează:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Triunghi dreptunghic. Din nou, putem începe cu una dintre cele trei tăieturi de-a lungul axei de simetrie.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Returnează:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Pentagon neregulat.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Returnări: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Un pătrat s-a rotit cu 45 de grade.
[]
Numai utilizatorii înregistrați pot participa la sondaj. , Vă rog.
Am rezolvat problema pt
-
în mai puțin de 10 minute
-
10-30 minute
-
30-60 minute
-
ore 1-2
-
in mai mult de 2 ore
-
alte
Au votat 42 de utilizatori. 47 utilizatori s-au abținut.
Sursa: www.habr.com