Sparing w Programowaniu Politechnika Poznańska, 10.03.2007

Opis

Razu pewnego żył sobie skąpy Król, ktory rozkazał swojemu Architektowi zbudowanie muru wokół zamku. Król był chciwy do tego stopnia, że nie chciał nawet słuchać propozycji swojego Architekta, który snuł wizję budowy pięknego muru z cegły, o doskonałym kształcie z ładnym wysokimi wierzami. Rozkazał, aby mur zbudowany został przy minimalnym nakładzie środków i pracy, ale jednocześnie nie znalazł się bliżej zamku niż pewien określony dystans. Gdyby Król dowiedział, że Architekt użył więcej kamienia niż było potrzebne do budowy muru spełniającego jego wymogi, zaraz skrócił by go o głowę. Dodatkowo zarządał od Architekta praktycznie "na wczoraj" wykaz niezbędnych materiałów do budowy muru.

Twoim zadaniem jest uratowanie biednego Architekta, przez napisanie programu, który wyliczy minimalną długość muru, który spełni wymagania Króla.

W zasadzie zadanie nie jest nawet takie trudne, gdyż zamek ma kształt wielokąta i stoi na płaskim podłożu. Architekt przygotował nawet układ Kartezjański, w którym można dokładnie określić współrzędne wszystkich wierzchołków zamku w stopach.

Specyfikacja wejścia

W pierwszej linii wejścia znajduje się liczba D (1 ≤ D ≤ 100) określająca liczbę testów.

Pierwsza linia testu zawiera dwie liczby N i L odzielone spacją. N (3 ≤ N ≤ 1000) jest liczbą wierzchołków królewskiego zamku, natomiast L (1 ≤ L ≤ 1000) jest minimalną odległością jaka musi być zachowana pomiędzy zamkiem a murem.

Kolejne N linii zawiera współrzędne wierzchołków zamku w porządku zgodnym z ruchem wskazówek zegara. Kaźda linia zawiera 2 liczby całkowite X_i i Y_i oddzielone spacją (-10000 ≤ X_i, Y_i ≤ 10000) reprezentujące współrzędne i-tego wierzchołka. Zamek nie ma dwóch takich samych wierzchołków, a boki zamku nie mają punktów wspólnych, poza wierzchołkami.

Specyfikacja wyjścia

Dla każdego przypadku testowego wypisz liczbę (w osobnej linii) reprezentującą minimalną możliwę długość muru w stopach, który spełni wymagania Króla. Musisz przedstawić wynik obliczeń w postaci liczby całkowitej, ponieważ nie wymyślono jeszcze liczb zmiennopozycyjnych. Musisz zaokrąglić do 8 cali - Król nie wybaczy większego błędu - przy czym jedna stopa to 12 cali.

Przykład

1
9 100
200 400
300 400
300 300
400 300
400 400
500 400
500 200
350 200
200 200

1628