U tragovima objavljujem zadatke iz Algoritamske staze (klasično sportsko programiranje. Za sat i pol potrebno je riješiti tri zadatka na Javi, C#, C++ ili Pythonu.)
1. Pita za šestero
Postavljanje zadatka
Maksimalno vrijeme — 4 sekunde.
Imate pitu. Kada je gledate odozgo, pita ima oblik (strogo) konveksnog mnogokuta. Dani su vam koordinate vrhova u cijelim brojevima X i Y.
Imate pet prijatelja. Želite podijeliti pitu na šest dijelova jednake površine (ali ne nužno jednakih oblika). Naravno, svatko može to učiniti s pet rezova, ali samo profesionalac može to učiniti s tri reza.
Pronađite tri rezna pravca kroz jednu točku koja će podijeliti pitu na šest dijelova jednake površine. Ispišite {x, y, d1, d2, d3}, gdje su (x, y) zajednička točka svih triju rezova, a d1, d2, d3 su kutovi smjera rezova u radijanima.
DefinicijaKlasa: CakeForSix
Metoda: cut
Parametri: int[], int[]
Vraća: double[]
Potpis metode: double[] cut(int[] x, int[] y)
(provjerite je li vaša metoda javna)
Napomene
- Pozitivni smjer duž osi x iznosi 0 (radijan), pozitivan smjer duž osi y iznosi pi/2 (radijan).
- Rez u smjeru d sličan je rezu u smjeru pi*k+d za bilo koji cijeli broj k.
- Možete prikazati bilo koje smjerove, oni ne moraju nužno biti unutar [0, pi).
- Grader će izračunati površine vaših šest komadića torte u doubles. Odgovor će biti prihvaćen ako je relativna ili apsolutna razlika između njih manja od 10^(-4).
- Točnije, neka X i Y budu najmanje i najveće od vaših šest područja, izračunatih od strane gradjera. Tada će vaš odgovor biti prihvaćen ako je Y < max(X + 10^(-4), X * 1 + 10^(-4))).
- (U izvornoj verziji zadatka korištena je točnost 1e-7 umjesto 1e-4. Da bi se riješio ovaj problem, u arhivi je granica točnosti smanjena zbog slučajeva poziva koji će vjerojatno učiniti zadatak neizvedivim s točnošću 1e-7. U idealnom svijetu ograničenja ne bi dopuštala takve slučajeve i još uvijek ne bi zahtijevala visoku točnost, pa je rješavanje problema s nekom općom numeričkom optimizacijom teško.)
Ograničenja
- x sadrži od 3 do 50 elemenata uključivo.
- y sadrži jednako toliko elemenata koliko i x.
- sve koordinate između 0 i 10 000 uključivo
- x i y definiraju konveksni mnogokotnik u smjeru suprotnom od kazaljke na satu.
Izvorna verzija na engleskom
Izjava o problemu
Maksimalno vrijeme je 4 sekunde.
Imate tortu. Gledajući odozgo, torta je (strogo) konveksni polygon. Dobivate koordinate njezinih vrhova u int[]x i y.
Imate pet prijatelja. Sada želite izrezati tortu na šest komada jednake površine (ali ne nužno jednakog oblika). Naravno, svatko to može učiniti sa pet rezova — ali samo pravi profesionalac to može učiniti u tri!
Pronađite tri ravna reza koja prolaze kroz istu točku i dijele tortu na šest jednakih dijelova. Vratite {x, y, d1, d2, d3}, gdje je (x, y) zajednička točka triju rezova, a d1, d2, d3 su njihovi smjerovi u radijanima.
Definicija
Klasa: CakeForSix
Metoda: cut
Parametri: int[], int[]
Vraća: double[]
Potpis metode: double[] cut(int[] x, int[] y)
(provjerite je li vaša metoda javna)
Napomene
— Pozitivan smjer duž x osi je 0 (radijani), pozitivan smjer duž y osi je pi/2 (radijani).
— Rez u smjeru d je isti kao rez u smjeru pi*k+d za bilo koji cijeli broj k.
— Možete vratiti bilo kakve smjerove, ne moraju biti iz [0,pi).
— Grader će izračunati površine vaših šest dijelova torte u doubleovima. Odgovor će biti prihvaćen ako je relativna ili apsolutna razlika između njih manja od 10^(-4).
— Preciznije, neka su X i Y najmanja i najveća od vaših šest površina, kako ih izračunava grader. Tada će vaš odgovor biti prihvaćen ako Y < max(X + 10^(-4), X * (1+10^(-4))).
— (Izvorna verzija problema koristila je preciznost 1e-7 umjesto 1e-4. Kako bi se ovaj problem riješio u arhivi, granica preciznosti je snižena zbog postojanja izazovnih slučajeva koji najvjerojatnije čine zadatak nerješivim s 1e-7 preciznosti. U idealnom svijetu, uvjeti ne bi trebali dopuštati takve slučajeve i još zahtijevati visoku preciznost, tako da nije lako riješiti problem putem neke opće numeričke optimizacije.)
Ograničenja
— x će imati između 3 i 50 elemenata, uključujući.
— y će imati isti broj elemenata kao x.
— Sve koordinate bit će između 0 i 10.000, uključujući.
— x i y će opisivati konveksni polygon u suprotnom smjeru kazaljke na satu.
Primjeri
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Vraća:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Simetričan, ali ne pravilan heksagon. Primjer odgovora odgovara rezanju preko horizonta i izvršavanju dvije druge rezove kroz sredinu, koje dijele svaki dio na tri dijela.
1)
{0, 1000, 0}
{0, 0, 1000}
Vraća:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Pravokutni trokut. Ponovno, možemo početi s jednim od triju rezova duž osi simetrije.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Vraća:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Nepravilan peterokut.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Vraća: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705}
Kvadrat, rotiran za 45 stupnjeva.
[]
Samo registrirani korisnici mogu sudjelovati u anketi. , molimo.
Riješio sam zadatak za
manje od 10 minuta
10-30 minuta
30-60 minuta
1-2 sata
više od 2 sata
drugo
Glasalo je 42 korisnika. Suzdržalo se 47 korisnika.
Izvor: habr.com
