Problem description

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]². Błąd względny zwracanych odpowiedzi na zapytania nie przekroczy 10⁻⁵.

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

Przykładowa interakcja

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