Circle

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$ $=$ $\{p$ $|$ $the$ $circle$ $with$ $center$ $p$ $and$ $radius$ $r$ $covers$ $C$ $\}$ .

Find the area of $S$ .

输入描述

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

For each test case, the first line contains two integers  and  separated by a single space denoting the number of vertices of the convex hull and the radius. If , the convex hull contains only  point. If , the convex hull is a line segment.

Each of the following  lines contains two integers  separated by a single space denoting a vertex at . 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  over all test cases does not exceed .

输出描述

Output a single decimal indicating the answer. Your answer will be considered correct if the absolute or relative error is no more than .

示例1

输入:

输出:

0.315146743628
0
31016.928202570849

原站题解

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

上一题

下一题

详情