Në gjurmët publikoj detyrat nga nënshkrimi Algorithm (programim sportiv klasik. Në një orë e gjysmë, duhet të zgjidhni tre detyra në Java, C#, C++ ose Python.)
1. Torta për gjashtë
Formulimi i detyrës
KohĂ«zgjatja maksimale â 4 sekonda.
Keni një tortë. Nëse e shihni nga lart, torta ka formën e një (strikt) poligoni konveks. Ju janë dhënë koordinatat e kulmëve në numra të plotë X dhe Y.
Keni pesë miq. Doni të ndani tortën në gjashtë pjesë me sipërfaqe të barabarta (por jo domosdoshmërisht të njëjta në formë). Sigurisht, kushdo mund ta bëjë këtë me pesë prerje, por vetëm profesionistët mund ta bëjnë këtë me tri prerje.
Gjeni tri prerje me vijat që kalojnë nëpër një pikë, të cilat do të ndanin tortën në gjashtë pjesë me sipërfaqe të barabarta. Nxirni {x, y, d1, d2, d3}, ku (x, y) është pika e përbashkët e të tre prerjeve, dhe d1, d2, d3 janë këndet e drejtimit të prerjeve në radiane.
PërkufizimiKlasë: CakeForSix
Metoda: cut
Parametrat: int[], int[]
Kthen: double[]
Nënshkrimi i metodës: double[] cut(int[] x, int[] y)
(sigurohuni që metoda juaj të jetë publike)
Shënime
- Kënd pozitiv përgjatë boshtit x është 0 (radian), kënd pozitiv përgjatë boshtit y është pi/2 (radian).
- Një prerje në drejtimin d është e ngjashme me një prerje në drejtimin pi*k+d për çdo numër të plotë k.
- Mund të nxirrni çdo drejtim; ato nuk duhet domosdoshmërisht të jenë nga [0, pi).
- Grader do të llogarisë sipërfaqet e gjashtë copa të tortës në double. Përgjigjja do të pranohet nëse ndarja relative ose absolute midis tyre është më e vogël se 10^(-4).
- Saktësisht, le të jenë X dhe Y më të voglat dhe më të mëdhatë nga gjashtë zonat tuaja, të llogaritura nga grader. Pastaj, përgjigjja juaj do të pranohet nëse Y <max (X+10^(-4), X*1+10^(-4))).
- (Në versionin origjinal të problemit, u përdor saktësia 1e-7 në vend të 1e-4. Për të zgjidhur këtë çështje, në arkiv, kufiri i saktësisë u uli për shkak të rasteve të thirrjeve që, me siguri, e bëjnë problemin të pazgjidhshëm me saktësi 1e-7. Në një botë ideale, kufizimet nuk duan të lejojnë raste të tilla dhe ende kërkojnë saktësi të lartë, kështu që zgjidhja e problemit përmes ndonjë optimizimi numëror të përgjithshëm nuk është e lehtë.)
Kufizimet
- x përmban nga 3 deri në 50 elemente përfshirë.
- y përmban të njëjtën sasi elementesh si x.
- të gjitha koordinatat midis 0 dhe 10,000 përfshirë
- x dhe y e përcaktojnë poligonin konveks në drejtimin kundër orës.
Origjinali në anglisht
Deklarata e Problemit
Kohëzgjatja është 4 sekonda.
Keni një tortë. E parë nga mbi, torta është një poligon (strikt) konveks. Jeni të dhënë koordinatat e kulmëve të saj në int[]s x dhe y.
Keni pesĂ« miq. Tani dĂ«shironi ta prisni tortĂ«n nĂ« gjashtĂ« copa me sipĂ«rfaqe tĂ« barabartĂ« (por jo domosdoshmĂ«risht me formĂ« tĂ« barabartĂ«). Sigurisht, kushdo mund ta bĂ«jĂ« atĂ« me pesĂ« prerje â por vetĂ«m njĂ« profesionist i vĂ«rtetĂ« mund ta bĂ«jĂ« atĂ« me tre!
Gjeni tri prerje të drejta që kalojnë përmes të njëjtit pikë që e ndajnë tortën në gjashtë pjesë të barabarta. Kthejeni {x, y, d1, d2, d3}, ku (x, y) është pika e përbashkët e tri prerjeve, dhe d1, d2, d3 janë drejtimet e tyre në radianca.
PĂ«rkufizimi
Klasë: CakeForSix
Metoda: cut
Parametrat: int[], int[]
Kthen: double[]
Nënshkrimi i metodës: double[] cut(int[] x, int[] y)
(sigurohuni që metoda juaj të jetë publike)
Shënime
â Drejtimi pozitiv pĂ«rgjatĂ« aksit x Ă«shtĂ« 0 (radianca), drejtimi pozitiv pĂ«rgjatĂ« aksit y Ă«shtĂ« pi/2 (radianca).
â NjĂ« prerje nĂ« drejtim d Ă«shtĂ« e njĂ«jtĂ« me njĂ« prerje nĂ« drejtim pi*k+d pĂ«r çdo numĂ«r tĂ« plotĂ« k.
â Mund tĂ« ktheni çdo drejtim, ato nuk duhet tĂ« jenĂ« nga [0,pi).
â Grader-i do tĂ« llogarisĂ« sipĂ«rfaqet e gjashtĂ« copave tĂ« tortĂ«s nĂ« double. PĂ«rgjigjja do tĂ« merret nĂ« konsideratĂ« nĂ«se dallimi relativ ose absolut midis tyre Ă«shtĂ« mĂ« i vogĂ«l se 10^(-4).
â MĂ« saktĂ«sisht, le tĂ« jenĂ« X dhe Y mĂ« tĂ« vogli dhe mĂ« tĂ« mĂ«dha nga gjashtĂ« sipĂ«rfaqet tuaja, siç Ă«shtĂ« llogaritur nga grader-i. AtĂ«herĂ«, pĂ«rgjigjja juaj do tĂ« merret nĂ« konsideratĂ« nĂ«se Y < max(X + 10^(-4), X * (1+10^(-4))).
â (Versioni origjinal i problemit pĂ«rdorte saktĂ«sinĂ« 1e-7 nĂ« vend tĂ« 1e-4. PĂ«r zgjidhjen e kĂ«tij problemi nĂ« arkiv kufiri i saktĂ«sisĂ« u ul pĂ«r shkak tĂ« ekzistencĂ«s sĂ« rasteve sfiduese qĂ« me shumĂ« gjasa e bĂ«nin detyrĂ«n tĂ« pazgjidhshme me saktĂ«si 1e-7. NĂ« njĂ« botĂ« ideale, kufizimet nuk do tĂ« lejonin raste tĂ« tilla dhe akoma do tĂ« kĂ«rkonin saktĂ«si tĂ« lartĂ«, kĂ«shtu qĂ« nuk do tĂ« ishte e lehtĂ« tĂ« zgjidhej problemi pĂ«rmes ndonjĂ« optimizimi tĂ« pĂ«rgjithshĂ«m numerik.)
Kufizimet
â x do tĂ« ketĂ« ndĂ«rmjet 3 dhe 50 elemente, pĂ«rfshirĂ«.
â y do tĂ« ketĂ« tĂ« njĂ«jtin numĂ«r elementesh si x.
â TĂ« gjitha koordinatat do tĂ« jenĂ« midis 0 dhe 10,000, pĂ«rfshirĂ«.
â x dhe y do tĂ« pĂ«rshkruajnĂ« njĂ« poligon konveks nĂ« rendin kundĂ«r-kthyer.
Shembuj
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Kthen:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Simetrik, por jo një gjeometri i saktë me gjashtë anë. Shembulli i përgjigjes përkon me ndarjen e tij në gjysmë në horizontal dhe kryerjen e dy prerjeve të tjera në qendër, të cilat ndajnë çdo pjesë në tre pjesë.
1)
{0, 1000, 0}
{0, 0, 1000}
Kthen:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Trekëndësh i drejtë. Përsëri, mund të fillojmë me njërën nga tre prerjet përgjatë aksit të simetrisë.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Kthen:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Pëntagon i pasaktë.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Kthen: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Katrori, i kthyer në 45 gradë.
[]
Vetëm përdoruesit e regjistruar mund të marrin pjesë në anketë. , ju lutem.
E zgjodha problemin për
më pak se 10 minuta
10-30 minuta
30-60 minuta
1-2 orë
më shumë se 2 orë
të tjera
Votuan 42 përdorues. U ndalën 47 përdorues.
Burimi: habr.com
