eolymp
bolt
Try our new interface for solving problems
Problems

Secret Island Base

Secret Island Base

Time limit 3 seconds
Memory limit 64 MiB

A group of ninjas want to set up a new secret base for training. For its location, they have selected a remote group of islands. In order to keep the base as covert as possible, they want to build it as far away from the coast as possible. To determine how suitable each island is in this respect, the ninjas have come to you for help.

You must write a program which is given the islands; they are modeled as polygons in flat space. For each island they wish to know the furthest away one could possibly get from the coastline. The distance from a point to the coastline is defined as the shortest Euclidean distance (i.e. distance in a straight line) from this point to a point on the coastline.

Of course, this must remain a secret. They promise they won't kill you, but do not discuss this with anyone! Upsetting a ninja is the last thing you (want to) do in this world.

Input data

The first line contains the number of islands to follow. Each island is given as follows:

  • One line with one integer n (3 n 20) - the number of vertices of the polygon describing the coastline of the island.

  • n lines, each with two integers x and y (-100x, y 100) - the coordinates of each vertex.

The vertices are given in counterclockwise order.

Output data

For every island in the input, the output should contain a single oating point number on a single line: the largest distance over which one can be separated from the coastline, while being on the island. Your answer should have either an absolute or a relative error of at most 10^{-3}.

Examples

Input example #1
1
3
0 0
10 0
3 8
Output example #1
2.7421536261
Source 2011 Benelux Algorithm Programming Contest, Preliminaries, Problem G