10135 - Herding Frosh

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Post by DJWS » Sat May 31, 2008 9:33 am

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
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

Post by DJWS » Thu Jun 05, 2008 7:21 am

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
New poster
Posts: 3
Joined: Mon Jun 20, 2011 3:53 pm

Re: 10135 - Herding Frosh

Post by kspilario » Mon Sep 12, 2011 4:04 am

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
New poster
Posts: 8
Joined: Thu Aug 21, 2014 12:03 am

Re: 10135 - Herding Frosh

Post by zholnin » Tue May 31, 2016 12:44 am

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.

Post Reply

Return to “Volume 101 (10100-10199)”