U tragovima Objavljujem probleme iz Algoritma (klasično sportsko programiranje. Za sat i po potrebno je riješiti tri problema u Javi, C#, C++ ili Pythonu.)
1. Pita za šest
Izjava o problemu
Vremensko ograničenje je 4 sekunde.
Imate pitu. Kada se gleda odozgo, kolač ima oblik (strogo) konveksnog poligona. Date su vam koordinate vrhova u X i Y cijelim brojevima.
Imaš pet prijatelja. Želite da podijelite pitu na šest komada jednake površine (ali ne nužno istog oblika). Naravno, svako to može učiniti u pet rezova, ali samo profesionalac to može učiniti u tri reza.
Nađite tri ravne linije kroz jednu tačku koje će podijeliti pitu na šest jednakih dijelova. Odštampajte {x, y, d1, d2, d3}, gdje je (x, y) zajednička tačka sva tri reza, a d1, d2, d3 su uglovi smjera rezova u radijanima.
definicijaKlasa: CakeForSix
Metoda: cut
Parametri: int[], int[] Povrati: double[] Potpis metode: double[] cut(int[] x, int[] y)
(uvjerite se da je vaša metoda javna)
Napomene
- Pozitivan smjer duž x-ose je 0 (radijani), pozitivni smjer duž y-ose je pi/2 (radijani).
- Rez u pravcu d je sličan rezu u pravcu pi*k+d za bilo koji cijeli broj k.
- Možete ispisati bilo koje smjernice, ne moraju biti od [0, pi).
- Ocjenjivač će izračunati površinu vaših šest komada torte u parovima. Odgovor će biti prihvaćen ako je relativna ili apsolutna razlika između njih manja od 10^(-4).
- Preciznije, neka X i Y budu najmanji i najveći od vaših šest površina koje je izračunao grejder. Tada će vaš odgovor biti prihvaćen ako Y
- (Originalna verzija problema koristila je preciznost 1e-7 umjesto 1e-4. Da bi se riješio ovaj problem u arhivi, granica preciznosti je smanjena zbog prisustva pozivanja slučajeva koji bi vjerovatno učinili problem nerješivim s preciznošću od 1e-7. U idealnom svijetu, granice ne dopuštaju takve slučajeve i još uvijek zahtijevaju visoku preciznost, tako da rješavanje problema nekom općom numeričkom optimizacijom nije lako.)
Ograničenja
- x sadrži od 3 do 50 elemenata uključujući.
- y sadrži isti broj elemenata kao i x.
- sve koordinate između 0 i 10 uključujući
- x i y definiraju konveksni poligon u smjeru suprotnom od kazaljke na satu.
Original na engleskom
Izjava o problemu
Vremensko ograničenje je 4 sekunde.
Imate tortu. Gledano odozgo, torta je (strogo) konveksan poligon. Date su vam koordinate njegovih vrhova u int[]sx i y.
Imaš pet prijatelja. Sada želite da isečete tortu na šest delova jednake površine (ali ne nužno istog oblika). Naravno, svako to može učiniti u pet rezova — ali samo pravi profesionalac to može učiniti u tri!
Nađite tri pravolinijska reza koja prolaze kroz istu tačku i koja je rezala tortu na šest jednako velikih dijelova. Povratak {x, y, d1, d2, d3}, gdje je (x, y) zajednička tačka tri rezanja, a d1, d2, d3 su njihovi smjerovi u radijanima.
definicija
Klasa: CakeForSix
Metoda: cut
Parametri: int[], int[] Povrati: double[] Potpis metode: double[] cut(int[] x, int[] y)
(uvjerite se da je vaša metoda javna)
bilješke
— Pozitivan smjer duž ose x je 0 (radijani), pozitivni smjer duž y ose je pi/2 (radijani).
— Rez u pravcu d je isti kao rez u pravcu pi*k+d za bilo koji ceo broj k.
— Možete vratiti bilo koje upute, ne moraju biti od [0,pi).
— Grejder će izračunati površine vaših šest komada kolača u duplo. Odgovor će biti prihvaćen ako je relativna ili apsolutna razlika između njih manja od 10^(-4).
— Preciznije, neka X i Y budu najmanja i najveća od vaših šest oblasti, kako je izračunao grejder. Tada će vaš odgovor biti prihvaćen ako je Y < max( X + 10^(-4), X * (1+10^(-4))).
— (Originalna verzija problema koristila je preciznost 1e-7 umjesto 1e-4. Za rješavanje ovog problema u arhivi granica preciznosti je smanjena zbog postojanja izazovnih slučajeva koji najvjerovatnije čine zadatak nerješivim sa preciznošću 1e-7 U idealnom svijetu ograničenja ne bi dopuštala takve slučajeve i još uvijek zahtijevaju 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 i x.
— Sve koordinate će biti između 0 i 10,000, uključujući.
— x i y će opisati konveksni poligon u smjeru suprotnom od kazaljke na satu.
primjeri
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Povratak:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Simetričan, ali nepravilan šestougao. Primjer odgovora odgovara vodoravnom rezanju na pola i pravljenju dva druga reza po sredini koji dijele svaki komad na tri dijela.
1)
{0, 1000, 0}
{0, 0, 1000}
Povratak:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Pravokutni trokut. Opet, možemo početi s jednim od tri reza duž ose simetrije.
2)
{40, 70, 90, 90, 50} {XNUMX} {XNUMX}
{30, 20, 40, 100, 60} {XNUMX} {XNUMX}
Povratak:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Nepravilan pentagon.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Povrati: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Kvadrat zarotiran za 45 stepeni.
[]
Samo registrovani korisnici mogu učestvovati u anketi. molim.
Rešio sam problem za
-
za manje od 10 minuta
-
10-30 minuta
-
30-60 minuta
-
1-2 sati
-
za više od 2 sata
-
drugi
Glasalo je 42 korisnika. Uzdržano je bilo 47 korisnika.
izvor: www.habr.com