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 grasslands. 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]
x_{1} y_{1} [coordinates of the first sheep]
...
x_{n} y_{n}
[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 4Warning: large Input/Output data, be careful with certain languages
hide comments
:
20140622 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!


Jens Stimpfle:
20140318 17:51:55
Haidar Abboud, if you tackle the problem the right way, there are no special cases to consider (repeatedpoints, lessthan3, allcolinear certainly are not).


Haidar Abboud:
20140313 14:53:22
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, lessthan3point inputs,...). When all the points are collinear, you have to return twice the distance between the furthest pair. Last edit: 20140313 15:01:35 

Abhimanyu:
20131227 17:58:31
got it accepted in 5.53s using Graham's scan. Couldn't believe it :') 

Sabina:
20130613 13:00:32
is it working right?


Hasil Sharma:
20130402 10:37:11
Applied the optimization technique , still getting TLE ...... help please 

FireBlade:
20130301 23:53:31
I am using Monotone Chain Convex Hull..still getting TLE..any pointers? 

simon:
20121212 16:16:23
@aditya kumar : The first, I would say :


simon:
20121212 16:15:10
does anyone think this is doable in python ? 

Boris Brinza:
20120921 14:09:17
20120525 16:04:54 Angelo Marletta

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