Domy mieszkańców Bajtocji mają kształty prostopadłościanów. Ze względu na postępujące przeludnienie ostatnio zaczęto budować je także wewnątrz jaskiń, których kształty nie są jednak dostosowane do prostopadłościennego budownictwa. W tej sytuacji rząd Bajtocji zwrócił się do Uni Bajtockiej o dofinansofanie opracowania programu komputerowego służącego do wyznaczania maksymalnej wielkości domu, jaki można wybudować wewnątrz wskazanej jaskini. Wniosek został rozpatrzony pozytywnie, a Ty zostałeś wyznaczony do realizacji tego projektu.
Musisz jeszcze wiedzieć, że jaskinie w Bajtocji mają jednakowy kształt na całej swojej długości (mają kształty "położonych" graniastosłupów), więc dla potrzeb tworzonego programu wystarczy znać kształt przekroju jaskini. Taki przekrój przez jaskinię składa się z jednego odcinka poziomego stanowiącego podłoże oraz ze sklepienia mającego kształt lini łamanej. Co więcej, linia ta ma taki kształt, że prosta pionowa poprowadzona z dowolnego punktu podłoża przecina ją w dokładnie jednym punkcie.
Oto przykładowa jaskinia z przykładowym położeniem domu:
W pierwszym wierszu danych wejściowych znajduje się pojedyncza liczba całkowita C oznaczająca liczbę zestawów danych. W kolejnych wierszach występuje kolejno C zestawów danych.
Opis zestawu danych składa się z liczby naturalnej N (2 ≤ N ≤ 200000) oznaczającej liczbę punktów wyznaczających linię łamaną sklepienia oraz następnie z N par liczb całkowitych (xi, yi) z zakresu od 0 do 2*109 oznaczających współrzędne kolejnych punktów (y1 = yN = 0). Punkty te wymienione są w kolejności od lewej do prawej (xi < xi+1).
Dane wejściowe składają się z N liczb rzeczywistych zaokrąglonych do trzech miejsc po przecinku – po jednej dla każdego zestawu danych wejściowych. Każda z tych liczb oznacza pole powierzchni przekroju największego domu, jaki można wybudować w danej jaskini.
3 5 0 0 2 1 4 3 6 2 7 0 6 0 0 5 5 7 3 10 3 14 6 17 0 6 0 0 2 5 4 5 8 1 13 4 18 0
6.000 37.500 16.350