Pas më po publikoj detyra nga pista Algorithm (programim sportiv klasik. Brenda një ore e gjysmë duhet të zgjidhni tri probleme me Java, C#, C++ ose Python.)
1. ĂmbĂ«lsirĂ« pĂ«r gjashtĂ«
Vendosja e detyrës
Limiti i kohës është 4 sekonda.
Keni një ëmbëlsirë. Nëse shikoni nga lart, ëmbëlsira ka formën e një shumëkëndësi (strikt) konveks.
Keni pesë miq. Dëshironi të ndani ëmbëlsirën në gjashtë pjesë me sipërfaqe të barabartë (por jo domosdoshmërisht me formë të njëjtë). Sigurisht, çdo njeri mund ta bëjë këtë me pesë prerje, por vetëm një profesionist mund ta bëjë me tre prerje.
Gjeni tri prerje nëpërmjet një pike, që ndajnë ëmbëlsirën në gjashtë pjesë të barabarta sipërfaqjeje. Kthejeni {x, y, d1, d2, d3}, ku (x, y) është pika e përbashkët e tre prerjeve, dhe d1, d2, d3 janë këndet e drejtimit të prerjeve në radian.
PĂ«rkufizimKlasa: 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ë boshtit x është 0 (radian), drejtimi pozitiv përgjatë boshtit y është pi/2 (radian).
- Një prerje në drejtimin d është e njëjtë me një prerje në drejtimin pi*k+d për çdo numër të plotë k.
- Mund të ktheni çdo drejtim, ato nuk duhet domosdoshmërisht të jenë nga [0, pi).
- Grader-i do të llogarisë sipërfaqet e gjashtë pjesëve tuaja të tortës në doubles. Përgjigjja do të pranohet nëse diferenca relative ose absolute midis tyre është më pak se 10^(-4).
- Më saktë, le të jenë X dhe Y më të voglat dhe më të mëdhatë nga gjashtë sipërfaqet tuaja, të llogaritura nga grader-i. Pastaj përgjigjja juaj do të pranohet nëse Y < max(X+10^(-4), X*1+10^(-4))).
- (Në versionin fillestar të problemit u përdor një saktësi 1e-7 në vend të 1e-4. Për të zgjidhur këtë problem në arkiv u ul kufiri i saktësisë për shkak të rasteve të thirrjeve, të cilat me siguri e bëjnë problemin të pa zgjidhshëm me saktësi 1e-7. Në një botë ideale, kufizimet nuk lejojnë raste të tilla dhe akoma kërkojnë saktësi të lartë, kështu që zgjidhja e problemit me ndonjë optimizim numëror të zakonshëm nuk është e lehtë.)
Kufizimet
- x përmban nga 3 deri në 50 elemente përfshirë.
- y përmban të njëjtën numër elementësh si x.
- të gjitha koordinatat janë midis 0 dhe 10,000 përfshirë
- x dhe y përcaktojnë një shumëkëndës konveks në drejtim të kundërt të orës.
Origjinali në anglisht
Deklarata e Problemit
Limiti i kohës është 4 sekonda.
Keni një ëmbëlsirë. Duke u parë nga lart, ëmbëlsira është një shumëkëndës (strikt) konveks. Ju janë dhënë koordinatat e majave të tij në int[]s x dhe y.
Keni pesĂ« miq. Tani dĂ«shironi ta prenoni Ă«mbĂ«lsirĂ«n nĂ« gjashtĂ« copa me sipĂ«rfaqe tĂ« barabartĂ« (por jo domosdoshmĂ«risht me formĂ« tĂ« njejtĂ«). Sigurisht, çdo kush mund ta bĂ«jĂ« kĂ«tĂ« me pesĂ« prerje â por vetĂ«m njĂ« profesionist i vĂ«rtetĂ« mund ta bĂ«jĂ« kĂ«tĂ« me tre!
Gjeni tri prerje të drejta që kalojnë nëpër të njëjtën pikë dhe që ndajnë ëmbëlsirën në gjashtë pjesë të barabarta nga pikëpamja e madhësisë. Kthejeni {x, y, d1, d2, d3}, ku (x, y) është pika e përbashkët e tre prerjeve, dhe d1, d2, d3 janë drejtime të tyre në radian.
PĂ«rkufizim
Klasa: 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Ă« boshtit x Ă«shtĂ« 0 (radian), drejtimi pozitiv pĂ«rgjatĂ« boshtit y Ă«shtĂ« pi/2 (radian).
â NjĂ« prerje nĂ« drejtimin d Ă«shtĂ« e njĂ«jtĂ« me njĂ« prerje nĂ« drejtimin pi*k+d pĂ«r çdo numĂ«r tĂ« plotĂ« k.
â Ju mund tĂ« ktheni çdo drejtim, ato nuk duhet tĂ« jenĂ« domosdoshmĂ«risht nga [0,pi).
â Grader do tĂ« llogarisĂ« sipĂ«rfaqet e gjashtĂ« copa tĂ« tuaja tĂ« tortĂ«s nĂ« dyfish. Pika do tĂ« pranohet nĂ«se diferenca relative ose absolute midis tyre Ă«shtĂ« mĂ« e vogĂ«l se 10^(-4).
â MĂ« saktĂ«sisht, le tĂ« jenĂ« X dhe Y mĂ« e vogla dhe mĂ« e madhe nga sipĂ«rfaqet tuaja gjashtĂ«, siç llogaritet nga grader. AtĂ«herĂ«, pĂ«rgjigjja juaj do tĂ« pranohet nĂ«se Y < max( X + 10^(-4), X * (1+10^(-4)) ).
â (Versioni origjinal i problemit pĂ«rdorte njĂ« saktĂ«si 1e-7 nĂ« vend tĂ« 1e-4. PĂ«r tĂ« zgjidhur kĂ«tĂ« problem nĂ« arkiv kufiri i saktĂ«sisĂ« Ă«shtĂ« ulur pĂ«r shkak tĂ« ekzistencĂ«s sĂ« rasteve sfiduese qĂ« me siguri e bĂ«jnĂ« detyrĂ«n tĂ« pazgjidhshme me saktĂ«sinĂ« 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 Ă«shtĂ« e lehtĂ« tĂ« zgjidhet problemi pĂ«rmes ndonjĂ« optimizimi tĂ« pĂ«rgjithshĂ«m numerik.)
Kufizimet
â x do tĂ« ketĂ« midis 3 dhe 50 elementeve, pĂ«rfshirĂ«.
â y do tĂ« ketĂ« tĂ« njĂ«jtin numĂ«r elementĂ«sh si x.
â TĂ« gjitha koordinatat do tĂ« jenĂ« midis 0 dhe 10,000, pĂ«rfshirĂ«.
â x dhe y do tĂ« pĂ«rshkruajnĂ« njĂ« poligon konvik.ânĂ« rend kundĂ«r orĂ«s.
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 }
Një hexagon simetrik, por jo të rregullt. Shembulli i përgjigjes është në përputhje me prerjen e saj në gjysmë horizontalisht dhe kryerjen e dy prerjeve të tjera në qendër, të cilat ndajnë secilën pjesë në tre pjesë.
1)
{0, 1000, 0}
{0, 0, 1000}
Kthen:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Një trekëndësh i drejtpërdrejtë. Përsëri, mund të fillojmë me një nga tre prerjet përgjatë akset të simetrisë.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Kthen:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Një pesëkëndësh i parregullt.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Kthen: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Një katror, i fuqizuar në 45 gradë.
[]
Vetëm përdoruesit e regjistruar mund të marrin pjesë në anketë. , ju lutemi.
E kam zgjidhur problemin për
më pak se 10 minuta
10-30 minuta
30-60 minuta
1-2 orë
më shumë se 2 orë
tjetër
42 përdorues votuan. 47 përdorues u abstenuan.
Burimi: habr.com
