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

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:-

hide comments
2016-01-18 08:26:36 CHANDAN KUMAR
My first convex hull problem really enjoying debugging it there are many corner cases but think systematically easy in one go
2016-01-18 05:03:20 Mayank Garg
My first convex hull problem ... enjoyed solving and debugging it ;)
2015-08-08 14:18:23 (Tjandra Satria Gunawan)(曾毅昆)
First time I implemented full version of my own convex hull algo written in C :)
2014-06-22 23:13:01
Beware of I/O cost. iostream, Java I/O etc. will easily add up to 1+ seconds on this data. Some of the data is very large!
Other than that, in order to get to the top ranks, employ some pruning strategies. During loading the data, try to perform a cheap bounding box check and only store data that isn't obviously inside.
2014-03-18 17:51:55 Jens Stimpfle
Haidar Abboud, if you tackle the problem the right way, there are no special cases to consider (repeated-points, less-than-3, all-colinear certainly are not).

- Do a stable sort + unique before searching a hull to remove the right repeated points.
- Find 2 half convex hulls as in most examples you find on the web. But don't find upper / lower half. Find left / right half, so that the right half hull starts with the bottommost then leftmost point.

edit: the halves should have the same endpoints contrary to some web examples.

Last edit: 2014-03-18 17:53:31
2014-03-13 14:53:22 Haidar Abboud
Any standard O(N log N) convex hull algorithm would be fine, but this problem offers all annoying details one can think of(collinear points, repeated point coordinates, less-than-3-point inputs,...). When all the points are collinear, you have to return twice the distance between the furthest pair.

Last edit: 2014-03-13 15:01:35
2013-12-27 17:58:31 Abhimanyu
got it accepted in 5.53s using Graham's scan. Couldn't believe it :')
2013-06-13 13:00:32 Sabina
is it working right?
dunno why tle all the time . does this program enter s"enter" at the end ???
2013-04-02 10:37:11 Hasil Sharma
Applied the optimization technique , still getting TLE ...... help please
2013-03-01 23:53:31 FireBlade
I am using Monotone Chain Convex Hull..still getting TLE..any pointers?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.