Na tropie publikuję zadania z toru Algorytm (klasyczne programowanie sportowe. W ciągu półtorej godziny należy rozwiązać trzy zadania w Java, C#, C++ lub Python.)
1. Ciasto dla sześciorga
Sformułowanie zadania
Limit czasu — 4 sekundy.
Masz ciasto. Jeśli patrzeć z góry, ciasto ma kształt (ściśle) wypukłego wielokąta. Dano ci współrzędne wierzchołków w liczbach całkowitych X i Y.
Masz pięciu przyjaciół. Chcesz podzielić ciasto na sześć części o równej powierzchni (ale niekoniecznie o takim samym kształcie). Oczywiście, każdy może to zrobić w pięć cięć, ale tylko profesjonalista potrafi to zrobić w trzy cięcia.
Znaleźć trzy cięcia prostymi liniami przez jeden punkt, które podzielą ciasto na sześć równych pod względem powierzchni części. Wypisz {x, y, d1, d2, d3}, gdzie (x, y) — wspólny punkt wszystkich trzech cięć, a d1, d2, d3 — kąty kierunku cięć w radianach.
DefinicjaKlasa: CakeForSix
Metoda: cut
Parametry: int[], int[]
Zwraca: double[]
Podpis metody: double[] cut(int[] x, int[] y)
(upewnij się, że twoja metoda jest publiczna)
Uwagi
- Dodatni kierunek wzdłuż osi x odpowiada 0 (radian), dodatni kierunek wzdłuż osi y odpowiada pi/2 (radian).
- Cięcie w kierunku d jest podobne do cięcia w kierunku pi*k+d dla dowolnej liczby całkowitej k.
- Możesz podać dowolne kierunki, nie muszą one koniecznie należeć do [0, pi).
- Grader obliczy powierzchnie twoich sześciu kawałków ciasta w double. Odpowiedź zostanie zaakceptowana, jeśli względna lub bezwzględna różnica między nimi jest mniejsza niż 10^(-4).
- Dokładniej, niech X i Y będą najmniejszymi i największymi z twoich sześciu obszarów, obliczonych przez grader. Wtedy twoja odpowiedź zostanie zaakceptowana, jeśli Y < max (X+10^(-4), X*1+10^(-4))).
- (W pierwotnej wersji zadania użyto dokładności 1e-7 zamiast 1e-4. Aby rozwiązać ten problem, w archiwum ograniczono dokładność z powodu istnienia przypadków wywołań, które najprawdopodobniej czynią zadanie nierozwiązywalnym z dokładnością 1e-7. W idealnym świecie ograniczenia nie powinny dopuszczać takich przypadków i nadal wymagać wysokiej dokładności, więc rozwiązanie problemu poprzez jakąś ogólną optymalizację numeryczną nie jest proste.)
Ograniczenia
- x zawiera od 3 do 50 elementów włącznie.
- y zawiera tyle samo elementów, co x.
- wszystkie współrzędne między 0 a 10 000 włącznie
- x i y definiują wypukły wielokąt w kierunku przeciwnym do ruchu wskazówek zegara.
Oryginał w języku angielskim
Opis problemu
Limit czasu wynosi 4 sekundy.
Masz ciasto. Widząc z góry, ciasto jest (ściśle) wypukłym wielokątem. Otrzymujesz współrzędne jego wierzchołków w tablicach int[] x i y.
Masz pięciu przyjaciół. Teraz chcesz pokroić ciasto na sześć kawałków o równej powierzchni (ale niekoniecznie równym kształcie). Oczywiście, każdy może to zrobić w pięciu cięciach — ale tylko prawdziwy profesjonalista potrafi zrobić to w trzech!
Znajdź trzy proste cięcia przechodzące przez ten sam punkt, które podzielą ciasto na sześć równych części. Zwróć {x, y, d1, d2, d3}, gdzie (x, y) to wspólny punkt trzech cięć, a d1, d2, d3 to ich kierunki w radianach.
Definicja
Klasa: CakeForSix
Metoda: cut
Parametry: int[], int[]
Zwraca: double[]
Podpis metody: double[] cut(int[] x, int[] y)
(upewnij się, że twoja metoda jest publiczna)
Uwagi
— Dodatni kierunek wzdłuż osi x to 0 (radiany), dodatni kierunek wzdłuż osi y to pi/2 (radiany).
— Cięcie w kierunku d jest takie samo jak cięcie w kierunku pi*k+d dla dowolnej liczby całkowitej k.
— Możesz zwrócić dowolne kierunki, nie muszą one pochodzić z [0,pi).
— Grader obliczy powierzchnie twoich sześciu kawałków ciasta jako liczby zmiennoprzecinkowe. Odpowiedź będzie akceptowana, jeśli względna lub bezwzględna różnica między nimi jest mniejsza niż 10^(-4).
— Dokładniej, niech X i Y będą najmniejszą i największą z twoich sześciu powierzchni, obliczonych przez grader. Twoja odpowiedź będzie akceptowana, jeśli Y < max(X + 10^(-4), X * (1+10^(-4))).
— (Oryginalna wersja problemu używała precyzji 1e-7 zamiast 1e-4. W celu rozwiązania tego problemu w archiwum ograniczenie precyzji zostało obniżone z powodu występowania przypadków wyzwań, które najprawdopodobniej czynią zadanie niesprzedowalnym przy precyzji 1e-7. W idealnym świecie ograniczenia nie pozwalałyby na takie przypadki i wciąż wymagałyby wysokiej precyzji, tak aby nie było łatwo rozwiązać problemu za pomocą ogólnej optymalizacji numerycznej.)
Ograniczenia
— x będzie miało od 3 do 50 elementów, włącznie.
— y będzie miało tę samą liczbę elementów co x.
— Wszystkie współrzędne będą miały wartości od 0 do 10 000, włącznie.
— x i y opiszą wypukły wielokąt w porządku przeciwnym do ruchu wskazówek zegara.
Przykłady
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Zwraca:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Symetryczny, ale nie regularny sześciokąt. Przykład odpowiedzi odpowiada przecięciu go na pół w poziomie i wykonaniu dwóch innych cięć w środku, które dzielą każdą część na trzy części.
1)
{0, 1000, 0}
{0, 0, 1000}
Zwraca:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Prostokątny trójkąt. Znowu, możemy zacząć od jednego z trzech cięć wzdłuż osi symetrii.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Zwraca:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Nierówny pięciokąt.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Zwraca: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705}
Kwadrat, obrócony o 45 stopni.
[]
Tylko zarejestrowani użytkownicy mogą brać udział w ankiecie. , proszę.
Rozwiązałem problem w
mniej niż 10 minut
10-30 minut
30-60 minut
1-2 godziny
więcej niż 2 godziny
inne
Głosowało 42 użytkowników. 47 użytkowników wstrzymało się.
Źródło: habr.com
