列表

详情


NC235156. 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 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 separated by a single space denoting the number of vertices of the convex hull and the radius. If , the convex hull contains only 1 point. If , the convex hull is a line segment.

Each of the following n lines contains two integers 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 .

示例1

输入:

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

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

上一题