Jalanjäljissä Julkaisen Algorithm-raidan ongelmat (klassinen urheiluohjelmointi. Puolessatoista tunnissa täytyy ratkaista kolme tehtävää Java-, C#-, C++- tai Python-kielellä.)
1. Piirakka kuudelle
Ongelma
Aikaraja on 4 sekuntia.
Sinulla on piirakka. Ylhäältä katsottuna kakku on (tiukasti) kuperan monikulmion muotoinen. Sinulle annetaan kärkien koordinaatit X- ja Y-kokonaislukuina.
Sinulla on viisi ystävää. Haluat jakaa piirakan kuuteen yhtä suureen osaan (mutta ei välttämättä saman muotoiseen). Tietysti kuka tahansa voi tehdä sen viidessä leikkauksessa, mutta vain ammattilainen voi tehdä sen kolmessa leikkauksessa.
Etsi kolme suoraa viivaa yhden pisteen läpi, jotka jakavat piirakan kuuteen yhtä suureen osaan. Tulosta {x, y, d1, d2, d3}, jossa (x, y) on kaikkien kolmen leikkauksen yhteinen piste ja d1, d2, d3 ovat leikkausten suuntakulmat radiaaneina.
MääritelmäLuokka: CakeForSix
Menetelmä: leikattu
Parametrit: int[], int[] Palauttaa: double[] Menetelmän allekirjoitus: double[] cut(int[] x, int[] y)
(varmista, että menetelmäsi on julkinen)
Huomautuksia
- Positiivinen suunta x-akselilla on 0 (radiaaneja), positiivinen suunta y-akselilla on pi/2 (radiaaneja).
- Leikkaus d-suunnassa on samanlainen kuin leikkaus suunnassa pi*k+d mille tahansa kokonaisluvulle k.
- Voit tulostaa mitä tahansa suuntia, niiden ei tarvitse olla lähtökohdasta [0, pi).
- Tiehöylä laskee kuuden kakkupalasi pinta-alan kaksinkertaisesti. Vastaus hyväksytään, jos niiden välinen suhteellinen tai absoluuttinen ero on pienempi kuin 10^(-4).
- Tarkemmin sanottuna olkoon X ja Y pienimmät ja suurimmat kuudesta tiehöylän laskemasta alueesta. Sitten vastauksesi hyväksytään, jos Y
- (Alkuperäinen ongelman versio käytti tarkkuutta 1e-7 1e-4 sijasta. Tämän ongelman ratkaisemiseksi arkistossa tarkkuusrajaa alennettiin kutsutapausten vuoksi, jotka todennäköisesti tekisivät ongelmasta ratkaisemattoman tarkasti 1e-7. Ihanteellisessa maailmassa rajat eivät salli tällaisia tapauksia ja vaativat silti suurta tarkkuutta, joten ongelman ratkaiseminen yleisellä numeerisella optimoinnilla ei ole helppoa.)
Rajoitukset
- x sisältää 3 - 50 elementtiä mukaan lukien.
- y sisältää saman määrän alkioita kuin x.
- kaikki koordinaatit välillä 0 ja 10 000 mukaan lukien
- x ja y määrittelevät kuperan monikulmion vastapäivään.
alkuperäinen englanniksi
Ongelmalausunto
Aikaraja on 4 sekuntia.
Sinulla on kakku. Ylhäältä katsottuna kakku on (tiukasti) kupera monikulmio. Sinulle annetaan sen kärkien koordinaatit int[]sx:ssä ja y:ssä.
Sinulla on viisi ystävää. Haluat nyt leikata kakun kuuteen yhtä suureen osaan (mutta ei välttämättä samanmuotoista). Tietysti kuka tahansa voi tehdä sen viidellä leikkauksella - mutta vain todellinen ammattilainen voi tehdä sen kolmella!
Etsi kolme saman pisteen läpi kulkevaa suoraviivaista leikkausta, jotka leikkaavat kakun kuuteen yhtä suureen osaan. Paluu {x, y, d1, d2, d3}, jossa (x, y) on kolmen leikkauksen yhteinen piste ja d1, d2, d3 ovat niiden suunnat radiaaneina.
Määritelmä
Luokka: CakeForSix
Menetelmä: leikattu
Parametrit: int[], int[] Palauttaa: double[] Menetelmän allekirjoitus: double[] cut(int[] x, int[] y)
(varmista, että menetelmäsi on julkinen)
Huomautuksia
— Positiivinen suunta x-akselilla on 0 (radiaania), positiivinen suunta y-akselilla on pi/2 (radiaania).
— Leikkaus suunnassa d on sama kuin leikkaus suunnassa pi*k+d mille tahansa kokonaisluvulle k.
— Voit palauttaa mitä tahansa reittiohjeita, niiden ei tarvitse olla lähtöpaikasta [0,pi).
— Tiehöylä laskee kuuden kakkupalasi pinta-alat kaksinkertaisesti. Vastaus hyväksytään, jos niiden välinen suhteellinen tai absoluuttinen ero on pienempi kuin 10^(-4).
— Tarkemmin sanottuna, olkoon X ja Y pienimmät ja suurimmat kuudesta alueestasi, kuten tiehöylä on laskenut. Sitten vastauksesi hyväksytään, jos Y < max( X + 10^(-4), X * (1+10^(-4)) ).
— (Tehtävän alkuperäisessä versiossa käytettiin tarkkuutta 1e-7 1e-4:n sijaan. Tämän ongelman ratkaisemiseksi arkistossa tarkkuusrajaa alennettiin, koska oli olemassa haastetapauksia, jotka todennäköisimmin tekevät tehtävästä ratkaisemattoman 1e-7 tarkkuudella Ihanteellisessa maailmassa rajoitukset eivät salli tällaisia tapauksia ja vaativat silti suurta tarkkuutta, joten ongelman ratkaiseminen yleisellä numeerisella optimoinnilla ei ole helppoa.)
rajoitteet
— x:ssä on 3–50 elementtiä.
— y:llä on sama määrä alkioita kuin x:llä.
— Kaikki koordinaatit ovat välillä 0–10,000 XNUMX, mukaan lukien.
— x ja y kuvaavat kuperaa monikulmiota vastapäivään.
Примеры
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Returns:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Symmetrinen mutta epäsäännöllinen kuusikulmio. Esimerkkivastaus vastaa sen leikkaamista puoliksi vaakasuoraan ja kahden muun leikkauksen tekemistä keskelle, jotka jakavat jokaisen palan kolmeen osaan.
1)
{0, 1000, 0}
{0, 0, 1000}
Returns:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Suorakulmainen kolmio. Jälleen voimme aloittaa yhdellä kolmesta leikkauksesta symmetria-akselilla.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Returns:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Epäsäännöllinen viisikulmio.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Palautus: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
45 astetta kierretty neliö.
[]
Vain rekisteröityneet käyttäjät voivat osallistua kyselyyn. , ole kiltti.
Ratkaisin ongelman
-
alle 10 minuutissa
-
10-30 minuuttia
-
30-60 minuuttia
-
1-2 tuntia
-
yli 2 tunnissa
-
muut
42 käyttäjää äänesti. 47 käyttäjää pidättyi äänestämästä.
Lähde: will.com