TopCoder Open 2019 challenge: gupitin ang pie sa anim na piraso

Sa daanan “Nanalo kami: TopCoder Open 2019” Nag-publish ako ng mga problema mula sa track ng Algorithm (classical sports programming. Sa isa't kalahating oras kailangan mong lutasin ang tatlong problema sa Java, C#, C++ o Python.)

1. Pie para sa anim

Pahayag ng problema

Ang limitasyon sa oras ay 4 na segundo.

May pie ka. Kung titingnan mula sa itaas, ang cake ay may hugis ng isang (mahigpit) convex polygon. Bibigyan ka ng mga coordinate ng vertices sa X at Y integers.

Mayroon kang limang kaibigan. Gusto mong hatiin ang pie sa anim na piraso ng pantay na lugar (ngunit hindi kinakailangang pareho ang hugis). Siyempre, kahit sino ay maaaring gawin ito sa limang pagbawas, ngunit isang pro lamang ang makakagawa nito sa tatlong pagbawas.

Maghanap ng tatlong hiwa sa mga tuwid na linya sa isang punto na hahatiin ang pie sa anim na pantay na bahagi. I-print ang {x, y, d1, d2, d3}, kung saan (x, y) ang karaniwang punto ng lahat ng tatlong hiwa, at ang d1, d2, d3 ay ang mga anggulo ng direksyon ng mga hiwa sa radian.

DepinisyonKlase: CakeForSix
Paraan: gupitin
Mga Parameter: int[], int[] Returns: double[] Method signature: double[] cut(int[] x, int[] y)
(siguraduhing pampubliko ang iyong pamamaraan)

Mga Tala

• Ang positibong direksyon sa kahabaan ng x-axis ay 0 (radians), ang positibong direksyon sa kahabaan ng y-axis ay pi/2 (radians).
• Ang isang hiwa sa d direksyon ay katulad ng isang hiwa sa pi*k+d na direksyon para sa anumang integer k.
• Maaari kang mag-output ng anumang mga direksyon, hindi nila kailangang mula sa [0, pi).
• Kakalkulahin ng grader ang lugar ng iyong anim na piraso ng cake sa doble. Ang sagot ay tatanggapin kung ang kamag-anak o ganap na pagkakaiba sa pagitan ng mga ito ay mas mababa sa 10^(-4).
• Mas tiyak, hayaan ang X at Y ang pinakamaliit at pinakamalaki sa iyong anim na lugar na kinakalkula ng grader. Kung gayon ang iyong sagot ay tatanggapin kung Y
• (Ang orihinal na bersyon ng problema ay gumamit ng katumpakan na 1e-7 sa halip na 1e-4. Upang malutas ang problemang ito sa archive, ibinaba ang limitasyon sa katumpakan dahil sa pagkakaroon ng mga kaso ng pagtawag na malamang na gagawing hindi malulutas ang problema nang may katumpakan. ng 1e-7. Sa isang perpektong mundo, hindi pinapayagan ng mga limitasyon ang mga ganitong kaso at nangangailangan pa rin ng mataas na katumpakan, kaya hindi madali ang paglutas ng problema sa ilang pangkalahatang pag-optimize ng numero.)

Paghihigpit

• x ay naglalaman ng mula 3 hanggang 50 elemento kasama.
• y ay naglalaman ng parehong bilang ng mga elemento bilang x.
• lahat ng mga coordinate sa pagitan ng 0 at 10 kasama
• Ang x at y ay tumutukoy sa isang matambok na polygon sa pakaliwa na direksyon.

Orihinal sa Ingles

Pahayag ng Suliranin

Ang limitasyon sa oras ay 4 segundo.

May cake ka. Kung makikita mula sa itaas, ang cake ay isang (mahigpit na) convex polygon. Bibigyan ka ng mga coordinate ng mga vertices nito sa int[]sx at y.

Mayroon kang limang kaibigan. Gusto mo na ngayong i-cut ang cake sa anim na piraso ng pantay na lugar (ngunit hindi kinakailangang pantay na hugis). Siyempre, magagawa iyon ng sinuman sa limang pagbawas — ngunit isang tunay na pro lang ang makakagawa nito sa tatlo!

Humanap ng tatlong straight-line cut na dumadaan sa parehong punto na naghiwa ng cake sa anim na pantay na malalaking bahagi. Ibalik ang {x, y, d1, d2, d3}, kung saan (x, y) ang karaniwang punto ng tatlong hiwa, at ang d1, d2, d3 ay ang kanilang mga direksyon sa radian.

Depinisyon

Klase: CakeForSix
Paraan: gupitin
Mga Parameter: int[], int[] Returns: double[] Method signature: double[] cut(int[] x, int[] y)
(siguraduhing pampubliko ang iyong pamamaraan)

Mga Tala
— Ang positibong direksyon sa kahabaan ng x axis ay 0 (radians), ang positibong direksyon sa kahabaan ng y axis ay pi/2 (radians).
— Ang isang hiwa sa direksyon d ay kapareho ng isang hiwa sa direksyon na pi*k+d para sa anumang integer k.
— Maaari kang bumalik sa anumang direksyon, hindi kailangang mula sa [0,pi).
— Kakalkulahin ng grader ang mga lugar ng iyong anim na piraso ng cake nang doble. Ang sagot ay tatanggapin kung ang kamag-anak o ganap na pagkakaiba sa pagitan ng mga ito ay mas mababa sa 10^(-4).
— Mas tiyak, hayaan ang X at Y ang pinakamaliit at pinakamalaki sa iyong anim na lugar, ayon sa pagkalkula ng grader. Pagkatapos, ang iyong sagot ay tatanggapin kung Y < max( X + 10^(-4), X * (1+10^(-4)) ).
— (Ang orihinal na bersyon ng problema ay gumamit ng 1e-7 precision sa halip na 1e-4. Para sa paglutas ng problemang ito sa archive ay ibinaba ang limitasyon sa katumpakan dahil sa pagkakaroon ng mga challenge case na malamang na ginagawang hindi malulutas ang gawain sa 1e-7 precision Sa isang perpektong mundo hindi papayagan ng mga hadlang ang mga ganitong kaso at nangangailangan pa rin ng mataas na katumpakan, upang hindi madaling lutasin ang problema sa pamamagitan ng ilang pangkalahatang pag-optimize ng numero.)

hadlang
— Ang x ay magkakaroon sa pagitan ng 3 at 50 elemento, kasama.
— y ay magkakaroon ng parehong bilang ng mga elemento bilang x.
— Ang lahat ng mga coordinate ay nasa pagitan ng 0 at 10,000, kasama.
— Ang x at y ay maglalarawan ng isang matambok na polygon sa magkasunod na pakaliwa.

Mga halimbawa

0)

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

Isang simetriko ngunit hindi regular na hexagon. Ang halimbawang sagot ay tumutugma sa pagputol nito sa kalahati nang pahalang at paggawa ng dalawang iba pang pagbawas sa gitna na naghahati sa bawat piraso sa tatlong piraso.

1)

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

Kanang tatsulok. Muli, maaari tayong magsimula sa isa sa tatlong hiwa sa kahabaan ng axis ng symmetry.

2)

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

Hindi regular na pentagon.

3)

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

Ang isang parisukat ay umiikot ng 45 degrees.

[Pinagmulan]

Ang mga rehistradong user lamang ang maaaring lumahok sa survey. Mag-sign in, pakiusap

Nalutas ko ang problema para sa

• mas mababa sa 10 minuto

• 10-30 minuto

• 30-60 minuto

• 1-2 na oras

• sa mahigit 2 oras

• iba

42 na user ang bumoto. 47 user ang umiwas.

Pinagmulan: www.habr.com