Śladami Publikuję zadania ze ścieżki Algorytm (klasyczne programowanie sportowe. W półtorej godziny musisz rozwiązać trzy problemy w języku Java, C#, C++ lub Python.)
1. Ciasto na szóstkę
Stwierdzenie problemu
Limit czasu wynosi 4 sekundy.
Masz ciasto. Ciasto widziane z góry ma kształt (ściśle) wypukłego wielokąta. Podano współrzędne wierzchołków w liczbach całkowitych X i Y.
Masz pięciu przyjaciół. Chcesz podzielić ciasto na sześć kawałków o równej powierzchni (ale niekoniecznie o tym samym kształcie). Oczywiście każdy może to zrobić w pięciu cięciach, ale tylko profesjonalista może to zrobić w trzech cięciach.
Znajdź trzy cięcia w liniach prostych przechodzących przez jeden punkt, które podzielą ciasto na sześć równych części. Wydrukuj {x, y, d1, d2, d3}, gdzie (x, y) jest punktem wspólnym wszystkich trzech cięć, a d1, d2, d3 to kąty kierunkowe cięć w radianach.
DefinicjaKlasa: CakeForSix
Metoda: cięcie
Parametry: int[], int[] Zwraca: double[] Sygnatura metody: double[] cut(int[] x, int[] y)
(upewnij się, że Twoja metoda jest publiczna)
Uwagi
- Dodatni kierunek wzdłuż osi x wynosi 0 (radiany), dodatni kierunek wzdłuż osi y to pi/2 (radany).
- Cięcie w kierunku d jest podobne do cięcia w kierunku pi*k+d dla dowolnej liczby całkowitej k.
- Możesz wyprowadzić dowolne kierunki, nie muszą one pochodzić z [0, pi).
- Równiarka obliczy powierzchnię sześciu kawałków ciasta w dwójkach. Odpowiedź zostanie przyjęta, jeśli względna lub bezwzględna różnica między nimi będzie mniejsza niż 10^(-4).
- Dokładniej, niech X i Y będą najmniejszymi i największymi z sześciu obszarów obliczonych przez oceniającego. Wtedy Twoja odpowiedź zostanie zaakceptowana, jeśli Y
- (W oryginalnej wersji problemu zastosowano precyzję 1e-7 zamiast 1e-4. Aby rozwiązać ten problem w archiwum, obniżono limit precyzji ze względu na obecność przypadków wywołujących, które prawdopodobnie sprawiłyby, że problemu nie dałoby się rozwiązać z precyzją 1e-7. W idealnym świecie ograniczenia nie pozwalają na takie przypadki i nadal wymagają dużej precyzji, więc rozwiązanie problemu za pomocą ogólnej optymalizacji numerycznej nie jest łatwe.)
Ograniczenia
- x zawiera od 3 do 50 elementów włącznie.
- y zawiera tę samą liczbę elementów co x.
- wszystkie współrzędne od 0 do 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
Problem Statement
Limit czasu wynosi 4 sekund.
Masz ciasto. Widziane z góry ciasto jest (ściśle) wypukłym wielokątem. Dane są współrzędne jego wierzchołków w int[]sx i y.
Masz pięciu przyjaciół. Teraz chcesz pokroić ciasto na sześć kawałków o równej powierzchni (ale niekoniecznie o równym kształcie). Oczywiście każdy może to zrobić w pięciu cięciach – ale tylko prawdziwy profesjonalista może to zrobić w trzech!
Znajdź trzy proste nacięcia przechodzące przez ten sam punkt, które przetną ciasto na sześć jednakowo dużych części. Zwróć {x, y, d1, d2, d3}, gdzie (x, y) jest punktem wspólnym trzech cięć, a d1, d2, d3 to ich kierunki w radianach.
Definicja
Klasa: CakeForSix
Metoda: cięcie
Parametry: int[], int[] Zwraca: double[] Sygnatura metody: double[] cut(int[] x, int[] y)
(upewnij się, że Twoja metoda jest publiczna)
Uwagi
— Dodatni kierunek wzdłuż osi x wynosi 0 (radiany), dodatni kierunek wzdłuż osi y to pi/2 (radany).
— 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 wskazówki, nie muszą one pochodzić z [0,pi).
— Równiarka obliczy pola sześciu kawałków ciasta w dwójkach. Odpowiedź zostanie przyjęta, jeśli względna lub bezwzględna różnica między nimi będzie mniejsza niż 10^(-4).
— Dokładniej, niech X i Y będą najmniejszymi i największymi z sześciu obszarów obliczonymi przez równiarkę. Wtedy Twoja odpowiedź zostanie zaakceptowana, jeśli Y < max( X + 10^(-4), X * (1+10^(-4)) ).
— (Oryginalna wersja problemu wykorzystywała precyzję 1e-7 zamiast 1e-4. Aby rozwiązać ten problem w archiwum, limit precyzji został obniżony ze względu na istnienie przypadków wyzwań, które najprawdopodobniej sprawiają, że zadania nie da się rozwiązać z precyzją 1e-7 W idealnym świecie ograniczenia nie pozwalałyby na takie przypadki i nadal wymagają dużej precyzji, więc nie jest łatwo rozwiązać problem za pomocą ogólnej optymalizacji numerycznej.)
ograniczenia
— x będzie zawierać od 3 do 50 elementów włącznie.
— y będzie miało taką samą liczbę elementów jak x.
— Wszystkie współrzędne będą wynosić od 0 do 10,000 XNUMX włącznie.
— x i y będą opisywać wypukły wielokąt w kolejności przeciwnej do ruchu wskazówek zegara.
Примеры
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 nieregularny sześciokąt. Przykładowa odpowiedź polega na przecięciu go poziomo na pół i wykonaniu dwóch innych cięć w środku, które dzielą każdy element na trzy części.
1)
{0, 1000, 0}
{0, 0, 1000}
Zwraca:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Trójkąt prostokątny. Ponownie 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 }
Nieregularny pięciokąt.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Zwroty: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Kwadrat obrócony o 45 stopni.
[]
W ankiecie mogą brać udział tylko zarejestrowani użytkownicy. , Proszę.
Rozwiązałem problem dla
-
w mniej niż 10 minut
-
10-30 minut
-
30-60 minut
-
1-2 godzin
-
za ponad 2 godziny
-
inny
Głosowało 42 użytkowników. 47 użytkowników wstrzymało się od głosu.
Źródło: www.habr.com