2815. Largest Empty Circle on a Segment

单点时限: 1.0 sec

内存限制: 256 MB

We are given line segments on the 2D plane. We want to find the maximum radius of an empty circle whose center coordinates are constrained as follows:

A circle is empty if no part of a segment is located strictly inside of it (thus, a segment may touch the circle, but may not intersect with the interior of the circle).

输入格式

The first line of the input file contains the number of test cases . The test cases are described next. The first line of a test case contains the integer numbers and (). The next lines of the test case contain integers each, describing the coordinates of the endpoints of a segment: , , and . The coordinates of the endpoints of the segment are and . All the coordinates are between and . Every two consecutive numbers on the same line are separated by a single blank.

输出格式

For each test case print a line containing a real number , denoting the maximum radius of an empty circle whose center obeys the constraints. The number must be printed with decimal digits (the number must be rounded up or down according to the usual rounding rules).

样例

Input
1
4 10
1 1 10 3
5 3 9 1
3 1 4 1
8 3 11 -3
Output
2.118

1 人解决,1 人已尝试。

1 份提交通过,共有 2 份提交。

9.2 EMB 奖励。

创建: 2 年,11 月前.

修改: 2 年,4 月前.

最后提交: 2 年前.

来源: SEERC 2010

题目标签