Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Help!

Limits 1s, 1.0 GB

I want to solve a simple enough problem, but I am so so busy that I don’t have enough time. So, could you please do it for me???

I have a some trees in a forest and I have a human to catch! I have to create an enclosed area using the trees as the vertices of a polygon in such a way that the human is trapped strictly inside the polygon (strictly inside means that if the human is on the boundary of the polygon, it’s not inside). Your job is to minimize the polygon’s perimeter.

Input

On the first line there will be an integer T (T <= 80), number of testcases. Then on the first line of each test case, there will be two integers X, Y (-106 <= X, Y <= 106), the position of the human. Then on the second line of each case, there will be an integer N (1<= N <= 100), number of trees in the forest. On the next N lines there will be two integers X, Y (-106 <= X, Y <= 106) on each line, the position of the trees.

Output

For each test case, you should output the case number and the minimum perimeter of the polygon in a new line. You have to print 6 digits (rounded) after the decimal point. If it’s impossible, print -1. See sample test cases for clarity.

Samples

InputOutput
2
2 1
3
4 0
0 3
0 0
5 0
2
0 0
10 0
Case 1: 12.000000
Case 2: -1

Discussion
Submit

Login to submit