TopCoder Open 2019 ülesanne: jagame piruka kuueks osaks

Jälgedel «Meie võitsime: TopCoder Open 2019» jagan ülesandeid Algoritmi rajalt (klassikaline spordiprogrammeerimine. Poolteist tundi peab lahendama kolm ülesannet Java, C#, C++ või Pythoniga.)

1. Kook kuuendale

Ülesande seadmine

Aja piirang – 4 sekundit.

Teil on kook. Kui vaadata pealt, on kook (rangelt) konvexse hulknurga kujuline. Teil on antud tippude koordinaadid täisarvudena X ja Y.

Teil on viis sõpra. Soovite jagada kooki kuue võrdselt suure (aga mitte tingimata sama kuju) osaks. Loomulikult suudab igaüks selle viie lõikega teha, kuid ainult pro suudab seda teha kolme lõikega.

Leidke kolm lõiget sirgete joontega läbi ühe punkti, mis jagavad kooki kuue võrdselt suure osa. Tagastage {x, y, d1, d2, d3}, kus (x, y) on kõigi kolme lõike ühispunkt ja d1, d2, d3 on lõikude suunad radiaanides.

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

Märkused

• Positiivne suund mööda x telge on 0 (radian), positiivne suund mööda y telge on pi/2 (radian).
• Lõige suunal d on samasugune nagu lõige suunal pi*k+d iga tervete arvu k korral.
• Saate esitada mis tahes suundi, need ei pea olema tingimata vahemikus [0, pi).
• Grader arvutab teie kuue torditüki pindalad doubles. Vastus on aktsepteeritud, kui suheline või absoluutne erinevus nende vahel on väiksem kui 10^(-4).
• Täpsemalt öeldes, las X ja Y olla teie kuue ala, mille grader on arvutanud, väikseim ja suurim. Siis on teie vastus aktsepteeritud, kui Y < max(X + 10^(-4), X * 1 + 10^(-4)).
• (Probleemi algses versioonis oli täpsus 1e-7 asemel 1e-4. Selle probleemi lahendamiseks arhiivis täpsuse piirmäära vähendamine toimus, kuna oli juhtumeid, mis tõenäoliselt muudavad ülesande lahendamise 1e-7 täpsusega võimatuks. Ideaalsetes tingimustes ei tohi piirangud selliseid juhtumeid lubada ja nad peaksid endiselt nõudma kõrget täpsust, seega ei ole selle probleemi lahendamine mingi üldise numbrilise optimeerimise abil lihtne.)

Piirangud

• x sisaldab 3 kuni 50 elementi (kaasa arvatud).
• y sisaldab sama palju elemente kui x.
• kõik koordinaadid vahemikus 0 kuni 10 000 (kaasa arvatud)
• x ja y defineerivad kumerat mitmekülgset vastupäeva.

Originaal inglise keeles

Probleemi kirjeldus

Aja limiit on 4 sekundit.

Sul on tort. Ülhäält vaadates on tort (täpselt) kumer polügoon. Teile on antud selle tipude koordinaadid int[] massiivides x ja y.

Sul on viis sõpra. Nüüd soovid torti lõigata kuue võrdsest pindalast tükiks (aga mitte tingimata võrdsest kujundist). Loomulikult on võimalik seda teha viie lõikega — kuid ainult tõeline professionaal suudab seda kolm korda teha!

Leia kolm sirgjoonelist lõiget, mis läbivad sama punkti ja lõikavad tordi kuue võrdsesse suurusesse ossa. Tagasta {x, y, d1, d2, d3}, kus (x, y) on kolme lõike ühine punkt ning 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 on avalik)

Märkused
— Positiivne suund x-teljel on 0 (radianit), positiivne suund y-teljel on pi/2 (radianit).
— Lõige suunas d on sama, mis lõige suunas pi*k+d, kus k on mis tahes täisarv.
— Sa võid tagastada ükskõik millised suunad, need ei pea olema vahemikus [0, pi).
— Hinnataja arvutab sinu kuue torditüki pindalad kahekümne täpsusega. Vastus võetakse vastu, kui suheline või absoluutne erinevus nende vahel on väiksem kui 10^(-4).
— Täpsemalt, olgu X ja Y sinu kuue pindala väikseim ja suurim, nagu hinnataja on arvutanud. Siis võetakse sinu vastus vastu, kui Y < max(X + 10^(-4), X * (1 + 10^(-4))).
— (Probleemi originaalversioon kasutas 1e-7 täpsust, mitte 1e-4. Selle probleemi arhiveerimise tähenduses alandati täpsuse piirangut, kuna eksisteerivad väljakutsed, mis tõenäoliselt muudavad ülesande lahendamise 1e-7 täpsusega impossibeilikuks. Ideaalses maailmas ei tohiks piirangud lubada selliseid juhtumeid ja samas nõuda kõrget täpsust, et probleemi ei oleks kerge lahendada mõne üldise arvutuskohandamise kaudu.)

Piirangud
— x massiivis on 3 kuni 50 elementi, sealhulgas.
— y massiivis on sama palju elemente kui x.
— Kõik koordinaadid jäävad vahemikku 0 kuni 10,000, sealhulgas.
— x ja y kirjeldavad kumerat polügooni vastupäeva suunas.

Näited

0)

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

Sümmeetriline, aga mitte õige kuusniit. Vastuse näide vastab sellele, kui jagada see horisontaalselt kahel pooleks ja teha kaks muud kärbet keskel, mis jagavad iga osa kolmeks osaks.

1)

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

Tõrvikute kolmnurk. Taaskord, saame alustada ühe kolmest lõikest sümmeetriatelje mööda.

2)

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

Vale viiekand.

3)

{300, 400, 300, 200}
{500, 600, 700, 600}
Tagastab: {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.

Lahendasin ülesande

• vähem kui 10 minutiga

• 10-30 minutit

• 30-60 minutit

• 1-2 tundi

• rohkem kui 2 tundi

• muu

Hääletas 42 kasutajat. Nõustusid 47 kasutajat.

Allikas: habr.com