Po stopinjah Objavljam naloge iz skladbe Algoritem (klasično športno programiranje. V uri in pol morate rešiti tri naloge v Javi, C#, C++ ali Pythonu.)
1. Pita za šest
Izjava o težavah
Časovna omejitev je 4 sekunde.
Imate pito. Gledano od zgoraj ima torta obliko (strogo) izbočenega mnogokotnika. Podane so koordinate oglišč v celih številih X in Y.
Imaš pet prijateljev. Pito želite razdeliti na šest kosov enake površine (vendar ne nujno enake oblike). Seveda lahko vsak naredi to v petih rezih, a le profesionalec lahko to naredi v treh rezih.
Poiščite tri premočrtne reze skozi eno točko, ki bodo pito razdelile na šest enakih delov. Izpiši {x, y, d1, d2, d3}, kjer je (x, y) skupna točka vseh treh rezov, d1, d2, d3 pa smerni koti rezov v radianih.
DefinicijaRazred: CakeForSix
Metoda: rez
Parametri: int[], int[] Vrne: double[] Podpis metode: double[] cut(int[] x, int[] y)
(prepričajte se, da je vaša metoda javna)
Opombe
- Pozitivna smer vzdolž osi x je 0 (radianov), pozitivna smer vzdolž osi y je pi/2 (radianov).
- Rez v smeri d je podoben rezu v smeri pi*k+d za katero koli celo število k.
- Izpišete lahko poljubna navodila, ni nujno, da so od [0, pi).
- Grader bo izračunal površino vaših šestih kosov torte v dvojih. Odgovor bo sprejet, če je relativna ali absolutna razlika med njima manjša od 10^(-4).
- Natančneje, naj bosta X in Y najmanjše in največje od vaših šestih območij, ki jih izračuna ocenjevalec. Potem bo vaš odgovor sprejet, če Y
- (Prvotna različica problema je uporabljala natančnost 1e-7 namesto 1e-4. Za rešitev tega problema v arhivu je bila meja natančnosti znižana zaradi prisotnosti klicnih primerov, zaradi katerih bi bila težava verjetno nerešljiva z natančnostjo od 1e-7. V idealnem svetu omejitve ne dovoljujejo takšnih primerov in še vedno zahtevajo visoko natančnost, zato reševanje problema s splošno numerično optimizacijo ni enostavno.)
Omejitve
- x vsebuje od 3 do vključno 50 elementov.
- y vsebuje enako število elementov kot x.
- vse koordinate med 0 in vključno 10
- x in y določata konveksni mnogokotnik v nasprotni smeri urinega kazalca.
original v angleščini
Izjava o težavi
Časovna omejitev je 4 sekunde.
Imate torto. Gledano od zgoraj je torta (strogo) konveksen mnogokotnik. Podane so koordinate njegovih oglišč v int[]sx in y.
Imaš pet prijateljev. Zdaj želite torto razrezati na šest kosov enake površine (vendar ne nujno enake oblike). Seveda lahko vsakdo to naredi v petih kosih — a le pravi profesionalec lahko to naredi v treh!
Poiščite tri ravne reze, ki gredo skozi isto točko in razrežejo torto na šest enako velikih delov. Vrni {x, y, d1, d2, d3}, kjer je (x, y) skupna točka treh rezov, d1, d2, d3 pa so njihove smeri v radianih.
Definicija
Razred: CakeForSix
Metoda: rez
Parametri: int[], int[] Vrne: double[] Podpis metode: double[] cut(int[] x, int[] y)
(prepričajte se, da je vaša metoda javna)
Opombe
— Pozitivna smer vzdolž osi x je 0 (radianov), pozitivna smer vzdolž osi y je pi/2 (radianov).
— Rez v smeri d je enak rezu v smeri pi*k+d za katero koli celo število k.
— Vrnete lahko poljubna navodila, ni nujno, da so iz [0,pi).
— Grader bo izračunal površine vaših šestih kosov torte v dvojih. Odgovor bo sprejet, če je relativna ali absolutna razlika med njima manjša od 10^(-4).
— Natančneje, naj bosta X in Y najmanjše in največje od vaših šestih območij, kot jih je izračunal ocenjevalec. Nato bo vaš odgovor sprejet, če je Y < max( X + 10^(-4), X * (1+10^(-4))).
— (Prvotna različica problema je uporabljala natančnost 1e-7 namesto 1e-4. Za rešitev te težave v arhivu je bila meja natančnosti znižana zaradi obstoja zahtevnih primerov, zaradi katerih je naloga najverjetneje nerešljiva z natančnostjo 1e-7 V idealnem svetu omejitve ne bi dopuščale takšnih primerov in še vedno zahtevajo visoko natančnost, tako da ni lahko rešiti problema s splošno numerično optimizacijo.)
Omejitve
— x bo imel od 3 do vključno 50 elementov.
— y bo imel enako število elementov kot x.
— Vse koordinate bodo med 0 in vključno 10,000.
— x in y bosta opisala konveksni mnogokotnik v nasprotni smeri urnega kazalca.
Primeri
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Vrnitev:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Simetričen, vendar nepravilen šesterokotnik. Primer odgovora ustreza temu, da ga vodoravno prerežete na pol in naredite dva druga reza po sredini, ki vsak kos razdelita na tri dele.
1)
{0, 1000, 0}
{0, 0, 1000}
Vrnitev:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Pravokotni trikotnik. Spet lahko začnemo z enim od treh rezov vzdolž simetrične osi.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Vrnitev:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Nepravilni peterokotnik.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Vrne: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Kvadrat se je zasukal za 45 stopinj.
[]
V anketi lahko sodelujejo samo registrirani uporabniki. , prosim.
Rešil sem problem za
-
v manj kot 10 minutah
-
10-30 minut
-
30-60 minut
-
1-2 ur
-
v več kot 2 urah
-
drugi
Glasovalo je 42 uporabnikov. 47 uporabnikov se je vzdržalo.
Vir: www.habr.com