TopCoder Open 2019 ülesanne: lõikame kooki kuueks osaks.

Jälgedel „Meie võitsime: TopCoder Open 2019“ avaldan ülesandeid algoritmi rajalt (klassikaline spordiprogrammeerimine. Poolteise tunni jooksul tuleb lahendada kolm ülesannet keeles Java, C#, C++ või Python.)

1. Tort kuuele

Ülesande seadmine

Aja limiit — 4 sekundit.

Teil on tort. Ükskõik millisest vaatenurgast vaadates, tort on (kindlasti) kumer mitmik. Teile on antud tippude koordinaadid täisarvudes X ja Y.

Teil on viis sõpra. Te soovite jagada tordi kuue võrdsesse pindala (aga mitte tingimata sama kujuga) ossa. Loomulikult võib igaüks selle teha viie lõikega, kuid ainult professionaal suudab seda teha kolme lõikega.

Leidke kolm lõiget sirgete joontega läbi ühe punkti, mis jagavad torti kuue võrdses pindalas osaks. Tootke {x, y, d1, d2, d3}, kus (x, y) on kõigi kolme lõike ühine punkt, ja d1, d2, d3 — lõikete suunad radiaanides.

MääratlusKlass: CakeForSix
Meetod: cut
Parameetrid: int[], int[]
Tagastab: double[]
Meetodi allkiri: double[] cut(int[] x, int[] y)
(veenduge, et teie meetod oleks avalik)

Märkus

• Positiivne suund x-teljel on 0 (radian), positiivne suund y-teljel on pi/2 (radian).
• Lõik suunas d on sama, mis lõik suunas pi*k+d igasuguste täisarvude k jaoks.
• Saate esitada mis tahes suundi, need ei pea tingimata olema vahemikus [0, pi).
• Hinnang arvutab teie kuue tükikese pindalad doubles. Vastus aktsepteeritakse, kui suhteline või absoluutne erinevus nende vahel on väiksem kui 10^(-4).
• Täpsemalt, olgu X ja Y teie kuue ala väikseim ja suurim, arvutatud hinnangu poolt. Siis aktsepteeritakse teie vastust, kui Y < max(X + 10^(-4), X * 1 + 10^(-4))).
• (Algversioonis kasutati täpsust 1e-7 asemel 1e-4. Selle probleemi lahendamiseks arhiivis vähendati täpsuse piiri, kuna esines juhtumeid, mis tõenäoliselt muudavad ülesande lahendamatu täpsusega 1e-7. Ideaalmaailmas ei tohiks piirangud selliseid juhtumeid lubada ja nõuavad endiselt kõrget täpsust, seega on selle probleemi lahendamine teda ühise numbrilise optimeerimise abil keeruline.)

Piirangud

• x sisaldab 3 kuni 50 elementi sealhulgas.
• y sisaldab sama arvu elemente nagu x.
• kõik koordinaadid vahemikus 0 kuni 10 000 sealhulgas
• x ja y määravad kumerat mitmikut vastupäeva.

Originaal inglise keeles

Probleemi määratlus

Ajalimiit on 4 sekundit.

Sul on kook. Pealt vaadates on kook (rangelt) konveksne polügoon. Sul on antud selle tippude koordinaadid int[]des x ja y.

Sul on viis sõpra. Soovid nüüd kooki lõigata kuue võrdselt suure (kuigi mitte tingimata võrdselt kuju) tükiks. Loomulikult saab seda teha viie lõikega — aga ainult tõeline proff oskab seda teha kolme lõikega!

Leia kolm sirgjoonelist lõiget, mis läbivad sama punkti ja jagavad kooki kuue võrdselt suureks osaks. Tagasta {x, y, d1, d2, d3}, kus (x, y) on kolme lõike ühine punkt, ja d1, d2, d3 on nende suunad radiaanides.

Määratlus

Klass: CakeForSix
Meetod: cut
Parameetrid: int[], int[]
Tagastab: double[]
Meetodi allkiri: double[] cut(int[] x, int[] y)
(veenduge, et teie meetod oleks avalik)

Märkused
— Positiivne suund x-teljel on 0 (radians), positiivne suund y-teljel on pi/2 (radians).
— Lõige suunal d on sama mis lõige suunal pi*k+d, kus k on mistahes täisarv.
— Sa võid tagastada mis tahes suundi, need ei pea olema vahemikus [0, pi).
— Hinnamismoodul arvutab su koogi kuue tükikese pindalad kahekordsete arvudena. Vastus aktsepteeritakse, kui nende suhteline või absoluutne erinevus on väiksem kui 10^(-4).
— Täpsemalt, olgu X ja Y su koogi kuue tükikese pindalade väikseim ja suurim, nagu arvutas hinnamismoodul. Siis aktsepteeritakse sinu vastust, kui Y < max(X + 10^(-4), X * (1+10^(-4))).
— (Probleemi originaalversioon kasutas 1e-7 täpsust, mitte 1e-4. Selle ülesande arhiivi ülelaskmiseks vähendati täpsuse piiri, kuna eksisteerib väljakutse juhtumeid, mis tõenäoliselt muudavad ülesande lahendamise 1e-7 täpsusega praktiliselt võimatuks. Ideaalsetes tingimustes ei lubaks nõuded selliseid juhtumeid ja siiski vajavad kõrget täpsust, mistõttu ei ole probleemi lihtne lahendada kasutades üldist numbrilist optimeerimist.)

Piirangud
— x sisaldab 3 kuni 50 elementi, sealhulgas.
— y-l on sama palju elemente kui x-l.
— Kõik koordinaadid on vahemikus 0 kuni 10,000, sealhulgas.
— x ja y kujutavad konveksset polügooni vastupäeva.

Näited

0)

{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Tagasta:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }

Sümmeetriline, kuid mitte regulaarne kuusnurks. Vastuse näide vastab kooki horisontaalselt pooleks lõhkumisele ja kahe teise lõike tegemisele keskelt, mis jagab iga osa kolmeks osaks.

1)

{0, 1000, 0}
{0, 0, 1000}
Tagasta:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }

Õiguslik kolmnurk. Jälle, saame alustada ühe kolmest lõikest sümmeetria telje mööda.

2)

{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Tagasta:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }

Ebaõige viiekand.

3)

{300, 400, 300, 200}
{500, 600, 700, 600}
Tagasta: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }

Ruut, pööratud 45 kraadi.

[Allikas]

Ainult registreeritud kasutajad saavad küsitluses osaleda. Logige sisse, palun.

Löin mure ära

• vähem kui 10 minutiga

• 10-30 minutit

• 30-60 minutit

• 1-2 tundi

• rohkem kui 2 tundi

• muid

Hääletas 42 kasutajat. Hoidusid 47 kasutajat.

Allikas: habr.com