Las

Treść

Republika Erjotki to odległy kraj znany przede wszystkim z ogromnej przepustowości łącz internetowych. Dzięki zastosowaniu najnowocześniejszych technologii problem czasu transmisji danych praktycznie tam nie występuje. Ostatnio dochodzi nawet do sytuacji, w których tradycyjne nośniki danych są wąskim gardłem w przepływie i przetwarzaniu informacji. Mało kto jednak wie, iż obywatele Erjotki troszczą się nie tylko o swoje hiper-światłowody. Równie ważna, o ile nie najważniejsza, jest tu dbałość o środowisko naturalne. Ekspansja przemysłowa dziewiętnastego i dwudziestego wieku doprowadziła do niemal całkowitego wycięcia pierwotnych lasów, porastających onegdaj ogromne połacie kraju. Nauczeni tym przykrym doświadczeniem Erjotczanie już od kilkudziesięciu lat prowadzą intensywny program zalesiania. Istotnym elementem tego programu są precyzyjne pomiary powierzchni lasów.

Metoda używana do obliczania pola powierzchni obszarów leśnych jest następująca. W pierwszym kroku wydzielone zostają poszczególne lasy tak, aby powierzchnię każdego z nich można było policzyć osobno. Dla pojedynczego lasu ustala się położenie każdego drzewa, w postaci punktu (x,y) w prostokątnym układzie współrzędnych. Jako przybliżenie lasu przyjmuje się najmniejszy wielokąt wypukły taki, że wszystkie drzewa leżą w jego wnętrzu, na krawędziach bądź w wierzchołkach. Pole powierzchni lasu jest zatem przybliżane polem powierzchni tak wyznaczonego wielokąta.

Przez ostatnie lata powierzchnia lasów była wyliczana ręcznie przez doświadczonych pracowników Lasów Erjockich. Niestety w tym roku odchodzą oni na zasłużoną emeryturę, a ich następcy nie są tak biegli jak starsi koledzy. W związku z tym postanowiono zautomatyzować proces wyznaczania powierzchni lasów przy użyciu kilku współpracujących ze sobą programów komputerowych. Tobie przypadło w udziale napisanie jednego z nich. Na podstawie współrzędnych wszystkich drzew rosnących w jednym lesie oblicz pole powierzchni tegoż lasu.

Wejście

Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1<=N<=20) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:

Jeden zestaw danych

Pierwszy wiersz zestawu danych zawiera liczbę całkowitą n (3<=n<=20 000) oznaczającą liczbę drzew w lesie. W kolejnych n wierszach znajdują się współrzędne drzew, podane jako pary liczb całkowitych x_i i y_i (0<=x_i,y_i<=100 000), oddzielonych pojedynczą spacją. Można założyć, że każde drzewo rośnie w innym punkcie, a w podanym zbiorze znajdują się co najmniej trzy punkty nie leżące na tej samej prostej.

Wyjście

Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu jest pole powierzchni lasu zaokrąglone w dół do najbliższej liczby całkowitej.

Przykład

dane wejściowe:
2
3
0 0
2 0
0 2
5
2 2
3 3
0 0
1 3
5 0

wynik:
2
10