Na stezce Zveřejňuji problémy ze stopy Algorithm (klasické sportovní programování. Během jedné a půl hodiny potřebujete vyřešit tři problémy v Javě, C#, C++ nebo Pythonu.)
1. Koláč pro šest
Formulace problému
Časový limit je 4 sekundy.
Máš koláč. Při pohledu shora má dort tvar (přísně) konvexního mnohoúhelníku. Dostanete souřadnice vrcholů v celých číslech X a Y.
Máte pět přátel. Chcete koláč rozdělit na šest kusů stejné plochy (ale ne nutně stejného tvaru). Na pět seků to zvládne samozřejmě každý, ale na tři seky to zvládne jen profík.
Najděte tři rovné řezy skrz jeden bod, které rozdělí koláč na šest stejných částí. Tisk {x, y, d1, d2, d3}, kde (x, y) je společný bod všech tří řezů a d1, d2, d3 jsou směrové úhly řezů v radiánech.
DefiniceTřída: CakeForSix
Metoda: řez
Parametry: int[], int[] Vrací: double[] Signatura metody: double[] cut(int[] x, int[] y)
(ujistěte se, že vaše metoda je veřejná)
Poznámky
- Kladný směr podél osy x je 0 (radiány), kladný směr podél osy y je pi/2 (radiány).
- Řez ve směru d je podobný řezu ve směru pi*k+d pro libovolné celé číslo k.
- Můžete vypsat libovolné směry, nemusí být od [0, pi).
- Srovnávač spočítá plochu vašich šesti kousků dortu ve dvojnásobcích. Odpověď bude přijata, pokud je relativní nebo absolutní rozdíl mezi nimi menší než 10^(-4).
- Přesněji, nechť X a Y jsou nejmenší a největší z vašich šesti oblastí vypočítaných srovnávačem. Vaše odpověď bude přijata, pokud Y
- (Původní verze problému používala přesnost 1e-7 místo 1e-4. K vyřešení tohoto problému v archivu byl limit přesnosti snížen kvůli přítomnosti případů volání, které by pravděpodobně způsobily, že problém nebude řešitelný s přesností z 1e-7. V ideálním světě limity takové případy neumožňují a stále vyžadují vysokou přesnost, takže řešení problému pomocí nějaké obecné numerické optimalizace není snadné.)
Omezení
- x obsahuje 3 až 50 prvků včetně.
- y obsahuje stejný počet prvků jako x.
- všechny souřadnice mezi 0 a 10 000 včetně
- x a y definují konvexní mnohoúhelník ve směru proti směru hodinových ručiček.
originál v angličtině
Problémové prohlášení
Časový limit je 4 sekundy.
Máš dort. Při pohledu shora je dort (přísně) konvexní mnohoúhelník. Dostanete souřadnice jeho vrcholů v int[]sx a y.
Máte pět přátel. Nyní chcete dort nakrájet na šest kusů stejné plochy (ale ne nutně stejného tvaru). Samozřejmě, že to zvládne každý v pěti řezech – ale jen opravdový profík to dokáže ve třech!
Najděte tři rovné řezy procházející stejným bodem, které rozdělují dort na šest stejně velkých částí. Návrat {x, y, d1, d2, d3}, kde (x, y) je společný bod tří řezů a d1, d2, d3 jsou jejich směry v radiánech.
Definice
Třída: CakeForSix
Metoda: řez
Parametry: int[], int[] Vrací: double[] Signatura metody: double[] cut(int[] x, int[] y)
(ujistěte se, že vaše metoda je veřejná)
Poznámky
— Kladný směr podél osy x je 0 (radiány), kladný směr podél osy y je pi/2 (radiány).
— Řez ve směru d je stejný jako řez ve směru pi*k+d pro libovolné celé číslo k.
— Můžete se vrátit libovolným směrem, nemusí být z [0,pi).
— Srovnávač spočítá plochy vašich šesti kousků dortu ve dvojnásobcích. Odpověď bude přijata, pokud je relativní nebo absolutní rozdíl mezi nimi menší než 10^(-4).
— Přesněji, nechť X a Y jsou nejmenší a největší z vašich šesti oblastí, jak je spočítá srovnávač. Poté bude vaše odpověď přijata, pokud Y < max( X + 10^(-4), X * (1+10^(-4)) ).
— (Původní verze problému používala přesnost 1e-7 místo 1e-4. Pro vyřešení tohoto problému v archivu byl limit přesnosti snížen kvůli existenci případů výzvy, které s největší pravděpodobností činí úlohu neřešitelnou s přesností 1e-7 V ideálním světě by omezení takové případy neumožňovala a stále by vyžadovala vysokou přesnost, takže není snadné vyřešit problém pomocí nějaké obecné numerické optimalizace.)
Omezení
— x bude mít 3 až 50 prvků včetně.
— y bude mít stejný počet prvků jako x.
— Všechny souřadnice budou mezi 0 a 10,000 XNUMX včetně.
— x a y budou popisovat konvexní mnohoúhelník v pořadí proti směru hodinových ručiček.
Příklady
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Vrací:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Symetrický, ale nepravidelný šestiúhelník. Příklad odpovědi odpovídá rozříznutí vodorovně na polovinu a vytvoření dvou dalších řezů ve středu, které rozdělují každý kus na tři kusy.
1)
{0, 1000, 0}
{0, 0, 1000}
Vrací:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Pravoúhlý trojuhelník. Opět můžeme začít jedním ze tří řezů podél osy symetrie.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Vrací:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Nepravidelný pětiúhelník.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Vrácení: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Čtverec otočený o 45 stupňů.
[]
Průzkumu se mohou zúčastnit pouze registrovaní uživatelé. , prosím.
Problém jsem vyřešil pro
-
za méně než 10 minut
-
10 30-minuty
-
30 60-minuty
-
Hodiny 1-2
-
za více než 2 hodiny
-
další
Hlasovalo 42 uživatelů. 47 uživatelů se zdrželo hlasování.
Zdroj: www.habr.com