Problem description

Back
Show PDF
Kosmiczna ochrona
(kosmiczna-ochrona)
Memory limit: 128 MB
Time limit: 5.00 s

To jest zadanie interaktywne.

Podczas rutynowego patrolu Sił Ochrony Kosmosu, ujawniono niezidentyfikowany wielokąt wypukły. Wywiad donosi, że wielokąt znajduje się w całości wewnątrz kwadratu o rogach (0,0), (1000,0), (0,1000), (1000,1000) włącznie z brzegiem (punkt (0,0) może być wierzchołkiem wielokąta), a ponadto wierzchołki tego wielokąta wszystkie leżą w punktach kratowych. Twoim celem będzie wyznaczenie rozmiaru tego incydentu, czyli pola niezidentyfikowanego wielokąta wypukłego.

W tym celu możesz skorzystać z wielu statków zwiadowczych. Każdy statek zwiadowczy przy starcie otrzymuje konkretne docelowe miejsce stacjonowania, a po osiągnięciu celu przysyła raport – odległość do najbliższego punktu wielokąta.

W tym roku budżet SOK pozwala na użycie 8 000 tego rodzaju statków. Czy sprostasz wyzwaniu i wypełnisz misję?

Interakcja

Dostępne są dwa rodzaje zapytań:

  • ? x y wyśle statek zwiadowczy w punkt (x,y) i wypisze na standardowe wejście raport z tego statku, czyli jeden wiersz zawierający jedną liczbę rzeczywistą, określającą odległość z punktu (x,y) do najbliższego punktu szukanego wielokąta;
  • ! p jest sposobem zwrócenia przez Ciebie wyniku całej misji, czyli p – pola szukanego wielokąta.

Należy pamiętać o opróżnianiu bufora wypisywania.

Ograniczenia

Możesz zadać co najwyżej 8 000 zapytań typu ?, musisz zadać dokładnie jedno zapytanie typu ! i bezpośrednio po nim zakończyć program.

Punkty z zapytań typu ? muszą się znajdować w kwadracie [−10 000,10 000]2. Błąd względny zwracanych odpowiedzi na zapytania nie przekroczy 10−5.

Twoja odpowiedź zostanie zaakceptowana, jeżeli błąd względny nie przekroczy 10−6.

Przykładowa interakcja

Input Output
? 2.00 3.00
0.000000
? 3.00 2.00
1.000000
? 5.00 7.00
1.414213
? 3.00 4.00
0.000000
! 6.00

Szukany wielokąt to prostokąt o wierzchołkach (2,3), (4,3), (4,6) i (2,6).