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
