BSHEEP - Build the Fence


At the beginning of spring all the sheep move to the higher pastures in the mountains. If there are thousands of them, it is well worthwhile gathering them together in one place. But sheep don't like to leave their grass-lands. Help the shepherd and build him a fence which would surround all the sheep. The fence should have the smallest possible length! Assume that sheep are negligibly small and that they are not moving. Sometimes a few sheep are standing in the same place. If there is only one sheep, it is probably dying, so no fence is needed at all...

Input


t [the number of tests <= 100]
[empty line]
n [the number of sheep <= 100000]
x1 y1 [coordinates of the first sheep]
...
xn yn
[integer coordinates from -10000 to 10000]
[empty line]
[other lists of sheep]

Text grouped in [ ] does not appear in the input file. Assume that sheep are numbered in the input order.

Output


o [length of circumference, rounded to 2 decimal places]
p1 p2 ... pk
[the sheep that are standing in the corners of the fence; the first one should be positioned bottommost and as far to the left as possible, the others ought to be written in anticlockwise order; ignore all sheep standing in the same place but the first to appear in the input file; the number of sheep should be the smallest possible]
[empty line]
[next solutions]

Example

Input:
8

5
0 0
0 5
10 5
3 3
10 0

1
0 0

3
0 0
1 0
2 0

4
0 0
0 0
0 1
1 0

3
0 0
0 1
1 0

6
0 0
-1 -1
1 1
2 2
3 3
4 4

2
10 0
0 0

7
-3 -4
2 -3
4 3
-4 2
0 5
2 -3
-1 4

Output:
30.00
1 5 3 2

0.00
1

4.00
1 3

3.41
1 4 3

3.41
1 3 2

14.14
2 6

20.00
2 1

26.98
1 2 3 5 4

Warning: large Input/Output data, be careful with certain languages

hide comments
Angelo Marletta: 2012-05-25 14:04:54

Here you can find a friendly explanation on how I got rank #1 on this problem
http://mindthenerd.blogspot.com/2012/05/fastest-convex-hull-algorithm-ever.html

Last edit: 2012-05-25 14:06:38
aditya kumar: 2011-11-17 13:10:05

0 0
5 0
10 0
5 5
what should be the answer in this case?
1 3 4 or
1 2 3 4

npenate: 2011-09-03 02:11:09

@Nasty
Just as point 4 (-4, 2) is positioned bottommost than point 1 (-3 -4) the answer must be
26.98
1 2 3 5 4
not -> 26.98
1 2 3 4 5
reads the output.
I think you should first sort by the y and later by the x

Last edit: 2011-09-03 02:13:10
- _ -: 2011-09-02 23:01:11

Last Sample Output:
The output should not be
26.98
4 1 2 3 5
?

Last edit: 2011-09-03 02:57:59
Kaustubh Karkare: 2011-05-07 21:16:23

why do i keep getting a TLE ? i'm using Graham Scan here ...

Riley: 2010-09-15 10:20:35

is the shape expected to be rectangular, or can we use the good old d=√(x2-x1)+(y2-y1) ?

Stephen Oberholtzer: 2009-11-17 21:18:09

Circumference only applies to a circle. I think it's likely that the expected output is the perimeter.


Added by:mima
Date:2004-06-01
Time limit:7s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:-