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.|

PZPI5 - Nadruk na płytce

Jasiu otrzymał zlecenie od znanego Bajtockiego producenta muzyki na opracowanie okładki na płytę (w bajtockim standardzie B-CD) z Muzyką Bardzo Nowoczesną. Jako, że czasu na realizację kontraktu zostało mu już niewiele, postanowił postawić na oryginalność. Nagryzmolił więc w edytorze grafiki Bardzo Oryginalny Obszar (ograniczony łamaną zamkniętą bez samoprzecięć) wypełniony w całości kolorem czarnym i podesłał swoje dzieło producentowi.

Co ciekawe, gryzmoł Jasia wszystkim się spodobał, gdyż uznano, że rewelacyjnie odzwierciedla klimat sprzedawanej muzyki. Podjęto nawet decyzję o umieszczeniu dzieła Jasia na górnej powierzchni samej płyty B-CD. Na płytce oczywiście znajdzie się tylko okrągły fragment dzieła (zakreślony cyrklem na kartce z wydrukiem gryzmołka).

Ponieważ tusz drukarski nanoszony na płytki B-CD jest niezwykle kosztowny, należy jak najszybciej ustalić ile dokładnie tuszu zostanie zużyte przy tworzeniu wydruku. Twoim zadaniem jest określenie powierzchni czarnego obszaru na płytce z Jasiowym nadrukiem.

Wejście

Pierwsza linia wejścia zawiera liczbę całkowitą t (t<=20). W kolejnych liniach podanych jest t przypadków testowych.

Każdy przypadek testowy rozpoczyna się od linii zawierającej dwie liczby całkowite: n r, oznaczające liczbę wierzchołków łamanej ograniczającej dzieło Jasia oraz promień okręgu będącego brzegiem płytki (3<=n<=100000, 1<=r<=20000). Przyjmujemy, że płytka ma środek w punkcie o współrzędnych (0,0). W kolejnych n liniach podane są po dwie liczby całkowite xi yi oznaczające współrzędne kolejnych wierzchołków łamanej Jasia, zgodnie z kierunkiem ruchu wskazówek zegara (-20000 <= xi,yi<= 20000).

Wyjście

Dla każdego przypadku testowego wypisz dokładnie jedną liczbę, oznaczającą pole powierzchni fragmentu figury Jasia, który znajduje się w obrębie podanego koła. Dopuszczalny jest błąd bezwzględny wyniku nie przekraczający 0.01.

Przykład

Wejście:
1
14 3
1 -1
0 0
0 1
-1 -1
1 -2
4 -1
1 -4
-3 1
0 3
3 3
-1 2
2 2
1 1
4 0

Wyjście:
15.6515

Ilustracja do przykładu w treści


Dodane przez:adrian
Data dodania:2005-05-21
Limit czasu wykonania programu:1.904s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:I Pomorskie Zawody w Programowaniu Indywidualnym - finał

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