408256: GYM103069 J Circle

Prof. Pang does research on the minimum covering circle problem. He does not like random algorithms so he decides to find an efficient deterministic one. He starts with the classical idea of binary search. In each iteration of the binary search, the following problem needs to be solved:

Given the radius $$$r$$$ of a circle and a convex hull $$$C$$$, let $$$S$$$ be defined as $$$$$$S=\{p\ |\ \text{the circle with center $p$ and radius $r$ covers $C$}\}.$$$$$$ Find the area of $$$S$$$.

The first line contains a single positive integer $$$T$$$ denoting the number of test cases.

For each test case, the first line contains two integers $$$n$$$ and $$$r$$$ ($$$1\le n\le 1000$$$, $$$1\le r\le 30000$$$) separated by a single space denoting the number of vertices of the convex hull and the radius. If $$$n=1$$$, the convex hull contains only $$$1$$$ point. If $$$n=2$$$, the convex hull is a line segment.

Each of the following $$$n$$$ lines contains two integers $$$x, y$$$ ($$$-10000\le x, y\le 10000$$$) separated by a single space denoting a vertex at $$$(x, y)$$$. It is guaranteed that no two vertices coincide and no three vertices are collinear. Vertices are listed in counter-clockwise order.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$200000$$$.

Output a single decimal indicating the answer. Your answer will be considered correct if the absolute or relative error is no more than $$$10^{-6}$$$.

3
4 1
0 0
1 0
1 1
0 1
4 1
0 0
1 1
0 2
-1 1
4 100
0 0
1 0
1 1
0 1

0.315146743628
0
31016.928202570849