Në gjurmët Unë publikoj probleme nga pista e Algoritmit (Programimi i sporteve klasike. Në një orë e gjysmë ju duhet të zgjidhni tre probleme në Java, C#, C++ ose Python.)
1. Byrek për gjashtë
Formulimi i problemit
Afati kohor është 4 sekonda.
Ju keni një byrek. Kur shikohet nga lart, torta ka formën e një shumëkëndëshi (rreptësisht) konveks. Ju janë dhënë koordinatat e kulmeve në numrat e plotë X dhe Y.
Ju keni pesë miq. Doni ta ndani byrekun në gjashtë pjesë me sipërfaqe të barabartë (por jo domosdoshmërisht të njëjtën formë). Sigurisht, çdokush mund ta bëjë atë në pesë prerje, por vetëm një profesionist mund ta bëjë atë në tre shkurtime.
Gjeni tre prerje në vija të drejta përmes një pike që do ta ndajë byrekun në gjashtë pjesë të barabarta. Shtypni {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ërcaktimKlasa: CakeForGjashtë
Metoda: prerje
Parametrat: int[], int[] Kthimet: double[] Nënshkrimi i metodës: double[] cut(int[] x, int[] y)
(sigurohuni që metoda juaj të jetë publike)
Shënimet
- Drejtimi pozitiv përgjatë boshtit x është 0 (radianët), drejtimi pozitiv përgjatë boshtit y është pi/2 (radianët).
- Një prerje në drejtimin d është e ngjashme me një prerje në drejtimin pi*k+d për çdo numër të plotë k.
- Ju mund të nxirrni çdo drejtim, ato nuk duhet të jenë nga [0, pi).
- Grader do të llogarisë sipërfaqen e gjashtë copave tuaja të tortës në dyshe. Përgjigja do të pranohet nëse diferenca relative ose absolute ndërmjet 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 gjashtë zonat tuaja të llogaritura nga notuesi. Atëherë përgjigja juaj do të pranohet nëse Y
- (Versioni origjinal i problemit përdori një saktësi prej 1e-7 në vend të 1e-4. Për të zgjidhur këtë problem në arkiv, kufiri i saktësisë u ul për shkak të pranisë së rasteve të thirrjeve që ka të ngjarë ta bëjnë problemin të pazgjidhshëm me një saktësi e 1e-7. Në një botë ideale, kufijtë nuk lejojnë raste të tilla dhe ende kërkojnë saktësi të lartë, kështu që zgjidhja e problemit me disa optimizime të përgjithshme numerike nuk është e lehtë.)
Kufizimet
- x përmban nga 3 deri në 50 elemente përfshirëse.
- y përmban të njëjtin numër elementesh si x.
- të gjitha koordinatat midis 0 dhe 10 përfshirëse
- x dhe y përcaktojnë një shumëkëndësh konveks në drejtim të kundërt të akrepave të orës.
origjinal në anglisht
Deklarata e Problemit
Afati kohor është 4 sekonda.
Ju keni një tortë. E parë nga lart, torta është një shumëkëndësh (rreptësisht) konveks. Ju janë dhënë koordinatat e kulmeve të saj në int[]sx dhe y.
Ju keni pesë miq. Tani dëshironi ta prisni tortën në gjashtë pjesë me sipërfaqe të barabartë (por jo domosdoshmërisht në formë të barabartë). Sigurisht, çdokush mund ta bëjë këtë në pesë shkurtime - por vetëm një profesionist i vërtetë mund ta bëjë atë në tre!
Gjeni tre prerje në vijë të drejtë që kalojnë nëpër të njëjtën pikë që e prenë tortën në gjashtë pjesë po aq të mëdha. Ktheni {x, y, d1, d2, d3}, ku (x, y) është pika e përbashkët e tre prerjeve dhe d1, d2, d3 janë drejtimet e tyre në radiane.
Përcaktim
Klasa: CakeForGjashtë
Metoda: prerje
Parametrat: int[], int[] Kthimet: double[] Nënshkrimi i metodës: double[] cut(int[] x, int[] y)
(sigurohuni që metoda juaj të jetë publike)
Shënimet
— Drejtimi pozitiv përgjatë boshtit x është 0 (radianët), drejtimi pozitiv përgjatë boshtit y është pi/2 (radianët).
— 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 të jenë nga [0,pi).
— Klasifikimi do të llogarisë sipërfaqet e gjashtë pjesëve tuaja të tortës në dyshe. Përgjigja do të pranohet nëse diferenca relative ose absolute ndërmjet tyre është më e vogël se 10^(-4).
— Më saktësisht, le të jenë X dhe Y më i vogli dhe më i madhi nga gjashtë zonat tuaja, siç llogaritet nga notuesi. Atëherë, përgjigja juaj do të pranohet nëse Y < max( X + 10^(-4), X * (1+10^(-4)) ).
— (Versioni origjinal i problemit përdori 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ë ekzistimit të rasteve sfiduese që me shumë gjasa 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 ende kërkojnë saktësi të lartë, kështu që nuk është e lehtë të zgjidhet problemi nëpërmjet një optimizimi të përgjithshëm numerik.)
kufizimet
— x do të ketë nga 3 deri në 50 elementë, 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ë shumëkëndësh konveks në rend të kundërt të akrepave të orës.
shembuj
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
kthimet:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Një gjashtëkëndësh simetrik por i çrregullt. Përgjigja e shembullit korrespondon me prerjen e saj në gjysmë horizontalisht dhe duke bërë dy prerje të tjera në qendër që e ndajnë secilën pjesë në tre pjesë.
1)
{0, 1000, 0}
{0, 0, 1000}
kthimet:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Trekëndësh kënddrejtë. Përsëri, mund të fillojmë me një nga tre prerjet përgjatë boshtit të simetrisë.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
kthimet:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Pentagoni i parregullt.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Kthimet: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Një katror rrotullohet 45 gradë.
[]
Vetëm përdoruesit e regjistruar mund të marrin pjesë në anketë. , te lutem
E zgjidha problemin për
-
në më pak se 10 minuta
-
Minuta 10-30
-
Minuta 30-60
-
1-2 orë
-
në më shumë se 2 orë
-
tjetër
42 përdorues kanë votuar. 47 përdorues abstenuan.
Burimi: www.habr.com