10135 - Herding Frosh

[DJWS]

I just see only few people who have solved this problem, however I think this problem it's not so hard. I have thought of a simple algorithm. If I miss something, please point out.

My algorithm is very simple. Just sort all points by their angles in polar coordinate system. Next, try to wrap all points in circular sequence and get a proper hull. In order to get the minimal hull, start wrapping from all different points, and see what is the minimal hull. Besides, the whole wrapping procedure is similar with Graham's scan.

Here is the explanation. However the origin (0,0) is outside of the initial convex hull or not, we can sort all points by their angle in polar coordinate system. If the origin (0,0) is outside of the initial convex hull, it means the origin must be a part of the wanted hull. In addition, the wanted hull is exactly a convex hull. So we can directly use Graham's scan within those well-sorted points. In my algorithm, all proper hulls are enumerated, and they must contain the wanted convex hull which is also the minimal hull. Furthermore, If the origin (0,0) is inside of the initial convex hull, the points are also well-sorted. We still can wrap the points in such sequence.

[DJWS]

I generate some test cases, please help verify them.

Code: Select all

10
0
1
0 0
1
1 1
2
0 1
0 2
2
0 -1
0 1
3
0 -1
0 0
0 1
3
0 0
0 1
0 2
3
0 -1
0 0
0 1
4
0 -2
0 -1
0 1
0 2
4
1 0
-1 0
0 1
0 -1

[kspilario]

My AC code had a runtime error for the case:
1
0 0
But for all other cases, here is my output (in order):
2.00

4.83

6.00

6.00

6.00

6.00

6.00

10.00

8.24

[zholnin]

I am lost.

Every single test in this thread. Lots of tests I invented myself. Thousands and thousands of random tests - everything matches with what uDebug produces and everything seems to work fine. And yes, I don't print additional line after input.

But still - WA. I am very frustrated. Here is the source:

http://pastebin.com/aZftLhQB

Any hints on which test it fails would be greatly appreciated!

EDIT:
Over last day I've run batches of randomized test each 1,000,000 cases against some solution which I found online and which gets AC.
Each batch was slightly different:
- floating number in input / integer numbers
- small number of points / large number of points
- small range of coordinates / large range of coordinates
- including point 0,0 and not including 0,0.

NO DIFFERENCES FOUNDS. So I don't see any options left. I submitted solution I found online - to check if it really gets AC and it did.
This website doesn't seem to be very active, so I don't expect to get response soon.