Sparing w Programowaniu Zespołowym UAM & PP, 6.11.2004

Opis

Na jednej z Twoich posiadłości znajduje się pewna liczba punktów wydobycia ropy. Do tej pory nie potrzebowałeś ogrodzenia wokół swojej działki, ale ostatnio gdy Twoje stosunki z sąsiadami się pogorszyły postanowiłeś ogrodzić to co dla ciebie najcenniejsze. Chcesz postawić płot w kształcie figury wypukłej tak aby wszystkie punkty znajdowały się wewnątrz ogrodzenia lub na jednym z boków. Interesuje Cię jakie jest minimalne pole ograniczone przez płot postawiony zgodnie z powyższymi wymaganiami.

Specyfikacja wejścia

W pierwszym wierszu znajduje się liczba D oznaczająca liczbę zestawów testowych. Dla każdego zestawu w pierwsyzm wierszu znajduje się pojedyncza liczba N (3 ≤ N ≤ 10^5) oznaczająca liczbę punktów wydobycia ropy, W kolejnych N liniach podane są współrzędne naturalne X, Y (0 ≤ X,Y ≤ 10^6) kolejnych punktów.

Specyfikacja wyjścia

Dla każdego zestawu danych wypisz w osobnej linii jedną linię zawierająca minimalną wartość pola, które może zostać ograniczone płotem zgodnie z warunkami zadania zaokrąglone do 3 miejsc po przecinku.

Przykład

2
3
0 3
3 0
0 0
4
0 0
1 0
0 1
2 2

4.500
2.000