Pėdsakais Skelbiu problemas iš Algoritmo takelio (klasikinis sporto programavimas. Per pusantros valandos reikia išspręsti tris uždavinius Java, C#, C++ arba Python kalbomis.)
1. Pyragas šešiems
Problemos teiginys
Laiko limitas yra 4 sekundės.
Turite pyragą. Žiūrint iš viršaus, pyragas yra (griežtai) išgaubto daugiakampio formos. Jums pateikiamos viršūnių koordinatės X ir Y sveikaisiais skaičiais.
Turi penkis draugus. Pyragą norite padalyti į šešis vienodo ploto gabalėlius (bet nebūtinai tos pačios formos). Žinoma, kiekvienas gali tai padaryti penkiais pjūviais, tačiau tik profesionalas gali tai padaryti trimis pjūviais.
Raskite tris tiesias pjūvius per vieną tašką, kuris padalins pyragą į šešias lygias dalis. Spausdinti {x, y, d1, d2, d3}, kur (x, y) yra bendras visų trijų pjūvių taškas, o d1, d2, d3 yra pjūvių krypties kampai radianais.
ApibrėžimasKlasė: „CakeForSix“.
Metodas: supjaustyti
Parametrai: int[], int[] Grąžina: double[] Metodo parašas: double[] cut(int[] x, int[] y)
(įsitikinkite, kad jūsų metodas yra viešas)
Pažymi,
- Teigiama kryptis išilgai x ašies yra 0 (radianai), teigiama kryptis išilgai y ašies yra pi/2 (radianais).
- Pjūvis d kryptimi yra panašus į pjūvį pi*k+d kryptimi bet kuriam sveikajam skaičiui k.
- Galite išvesti bet kokias kryptis, jos neturi būti nuo [0, pi).
- Greideris apskaičiuos jūsų šešių torto gabalėlių plotą dvigubai. Atsakymas bus priimtas, jei santykinis arba absoliutus skirtumas tarp jų yra mažesnis nei 10^(-4).
- Tiksliau, tegul X ir Y yra mažiausi ir didžiausi iš šešių greiderio apskaičiuotų plotų. Tada jūsų atsakymas bus priimtas, jei Y
- (Pradinėje problemos versijoje tikslumas buvo 1e-7, o ne 1e-4. Norint išspręsti šią problemą archyve, tikslumo riba buvo sumažinta, nes buvo iškvietimo atvejų, dėl kurių problema greičiausiai būtų neišsprendžiama tiksliai 1e-7. Idealiame pasaulyje ribos neleidžia tokių atvejų ir vis tiek reikalauja didelio tikslumo, todėl išspręsti problemą naudojant tam tikrą bendrą skaitmeninį optimizavimą nėra lengva.)
Apribojimai
- x yra nuo 3 iki 50 elementų imtinai.
- y yra toks pat elementų skaičius kaip ir x.
- visos koordinatės nuo 0 iki 10 000 imtinai
- x ir y apibrėžia išgaubtą daugiakampį prieš laikrodžio rodyklę.
Originalas anglų kalba
Problemos pareiškimas
Laiko limitas yra 4 sekundės.
Turite tortą. Žiūrint iš viršaus, pyragas yra (griežtai) išgaubtas daugiakampis. Jums pateikiamos jo viršūnių koordinatės int[]sx ir y.
Turi penkis draugus. Dabar tortą norite supjaustyti į šešias vienodo ploto gabalėlius (bet nebūtinai vienodos formos). Žinoma, kiekvienas gali tai padaryti penkiais pjūviais, bet tik tikras profesionalas gali tai padaryti trimis!
Raskite tris tiesius pjūvius, einančius per tą patį tašką, per kurį pyragas supjaustomas į šešias vienodas dideles dalis. Grąžinimas {x, y, d1, d2, d3}, kur (x, y) yra bendras trijų pjūvių taškas, o d1, d2, d3 yra jų kryptys radianais.
Apibrėžimas
Klasė: „CakeForSix“.
Metodas: supjaustyti
Parametrai: int[], int[] Grąžina: double[] Metodo parašas: double[] cut(int[] x, int[] y)
(įsitikinkite, kad jūsų metodas yra viešas)
pastabos
— Teigiama kryptis išilgai x ašies yra 0 (radianais), teigiama kryptis išilgai y ašies yra pi/2 (radianais).
— Bet kurio sveikojo skaičiaus k pjūvis d kryptimi yra toks pat kaip pjūvis pi*k+d kryptimi.
— Galite grąžinti bet kokias nuorodas, jos nebūtinai turi būti nuo [0,pi).
— Greideris apskaičiuos jūsų šešių torto gabalėlių plotus dvigubai. Atsakymas bus priimtas, jei santykinis arba absoliutus skirtumas tarp jų yra mažesnis nei 10^(-4).
— Tiksliau, tegul X ir Y yra mažiausias ir didžiausias iš šešių sričių, kurias apskaičiavo greideris. Tada jūsų atsakymas bus priimtas, jei Y < max( X + 10^(-4), X * (1+10^(-4)) ).
— (Pradinėje problemos versijoje buvo naudojamas 1e-7 tikslumas, o ne 1e-4. Šiai problemai išspręsti archyve tikslumo riba buvo sumažinta dėl iššūkių atvejų, dėl kurių užduotis greičiausiai neišsprendžiama 1e-7 tikslumu. Idealiame pasaulyje apribojimai neleistų tokių atvejų ir vis tiek reikalauja didelio tikslumo, todėl nėra lengva išspręsti problemą naudojant tam tikrą bendrą skaitmeninį optimizavimą.)
Suvaržymai
— x turės nuo 3 iki 50 elementų imtinai.
— y turės tokį patį elementų skaičių kaip ir x.
— Visos koordinatės bus nuo 0 iki 10,000 XNUMX imtinai.
— x ir y apibūdins išgaubtą daugiakampį prieš laikrodžio rodyklę.
pavyzdžiai
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Grąžinimas:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Simetriškas, bet netaisyklingas šešiakampis. Atsakymo pavyzdyje reikia perpjauti jį per pusę horizontaliai ir dar du pjūvius centre, padalijančius kiekvieną dalį į tris dalis.
1)
{0, 1000, 0}
{0, 0, 1000}
Grąžinimas:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Taisyklingas trikampis. Vėlgi, galime pradėti nuo vieno iš trijų pjūvių išilgai simetrijos ašies.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Grąžinimas:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Netaisyklingas penkiakampis.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Grąžina: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Kvadratas pasuktas 45 laipsnių kampu.
[]
Apklausoje gali dalyvauti tik registruoti vartotojai. , Prašau.
Aš išsprendžiau problemą už
-
per mažiau nei 10 minutes
-
10-30 minučių
-
30-60 minučių
-
1-2 valandos
-
per daugiau nei 2 valandas
-
kitas
Balsavo 42 vartotojai. 47 vartotojų susilaikė.
Šaltinis: www.habr.com