Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_31_02 - Sylwester w Bajtogrodzie

W Bajtogrodzie trwają przygotowania na sylwestra.  Prezydent miasta zażyczył sobie, aby w tym roku dookoła barierek zabezpieczających obszar przeznaczony do zabawy ustawiono mnóstwo kolorowych kwiatów. Jako współorganizator imprezy Twoim zadaniem jest policzenie długości obwodu po zewnętrznej i wewnętrznej stronie zabezpieczeń, aby było wiadomo ile kwiatów należy przywieźć.

Plac przeznaczony do zabawy jest wielokątem reprezentowanym przez N punktów dodatnich. Zabezpieczenia są kwadratami o boku długości 1 i ustawiane są zawsze na liniach łączących kolejne punkty. Ich pozycjonowanie jest zgodne z algorytmem rasteryzacji krzywych płaskich, więc fragmenty ogrodzenia mogą wystawać poza obszar ograniczony linią. W danej kratce może stać tylko jedno zabezpieczenie.

Punkty zostały podane w odpowiedniej kolejności. Dane są tak dobrane, aby zrasteryzowane linie się nie przecinały(mogą się nakładać). Ostatni punkt połączony jest z pierwszym. Czasem prezydent życzy sobie, aby zostało przygotowane miejsce wydzielone dla specjalnych gości.

Wejście

W pierwszej linii jedna liczba T(1<T<103) oznaczająca liczbę testów. Dalej dla każdego testu jedna liczba N(2<N<103) stanowiąca liczbę punktów ograniczających pole zabawy. Następnie są podane punkty w formacie X Y(0<X,Y<109). Dane wejściowe są tak dobrane, że wynik nigdy nie przekroczy 8×106.

Wyjście

Jedna liczba będąca sumą obwodów wewnątrz i zewnątrz zabezpieczeń.

Przyklad

Input:
2 3 2 3 5 1 8 5 4 1 1 1 3 3 3 3 1
Output:

34 
16 

 

Wyjasnienie

Dla pierwszego testu obwód wew=10, zew=24

Dla drugiego testu obwód wew=4, zew=12

Uwaga! Zakłada się, że obwody są zawsze niezerowe.


Dodane przez:Bartosz Rychcik
Data dodania:2017-01-06
Limit czasu wykonania programu:0.5s-3.400s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:GAWK MAWK BASH BC C NCSHARP CSHARP C++ 4.3.2 CPP CPP14 C99 COFFEE DART FORTH HASK JAVA JULIA KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PHP PROLOG PYTHON PYPY PYPY3 PYTHON3 PY_NBC R RACKET RUBY SQLITE SWIFT UNLAMBDA
Pochodzenie:ALGOLIGA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.