10256 - The Great Divide

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

Moderator: Board moderators

ntrhieu
New poster
Posts: 21
Joined: Mon Oct 22, 2001 2:00 am

10256 - The Great Divide

Post by ntrhieu »

The problem is not clearly stated. If anyone has read this problem, please clarify the following for me:

I am not sure if it is possible for a house to be on the deviding line ? There are two cases that I don't know what the answer should be (Yes/ No):
1) Two coincide points, each should be on different side of the line.
2) All the points are colinear.

My algorithms is pretty straight forward: check if the two convex hulls of the two sets of points intersect (have a least one point in common) or not. But I got WA. Is there any tricks ? Hope someone can figure it out for me.

Thanks
Hieu Nguyen

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann »

How do you determine if the two convex hulls intersect? Do you check the case that one hull is completely contained in the other? (I haven't solved it yet, but maybe I can help guessing ;-))

ntrhieu
New poster
Posts: 21
Joined: Mon Oct 22, 2001 2:00 am

Post by ntrhieu »

Yes, I did check that case.
First, I check if the two convex hulls have any two edges intersect (including endpoints), then I check if any vertices of one hull inside (or on edge or coincide with some vertex) of the other hull.
If either check returns true, then it's indivisible(No), else it is divisible (Yes)
Hieu Nguyen

dh3014
New poster
Posts: 24
Joined: Tue Mar 26, 2002 2:00 am
Location: Taiwan
Contact:

same question

Post by dh3014 »

I have the same question to this problem.
who has the correct output for following input data:
--
2 2
0 0
0 1
1 0
1 1
2 2
0 0
1 1
0 1
1 0
1 1
100 100
100 100
1 1
100 100
100 101
1 2
1 0
3 0
2 0
1 2
2 0
3 0
1 0
4 1
0 0
0 2
2 2
2 0
1 1
4 4
0 0
10 0
10 10
0 10
2 4
4 2
4 4
2 2
2 2
0 0
0 1
0 6
0 1
2 2
0 0
0 2
0 6
0 1
2 2
0 0
0 2
0 6
0 3
0 0
----
My program's output is:
---
Yes
No
No
Yes
Yes
No
No
No
No
No
Yes
---
who can tell which is not correct or provide any other test datas?

ahanys
New poster
Posts: 24
Joined: Mon Nov 19, 2001 2:00 am
Location: N/A
Contact:

Solution to this problem!!!!

Post by ahanys »

You find the 2 convex hulls, each for one set of houses and determine whether the each point of one convex hull is inside of another and on the contrary. If there is any point that print NO else print YES. :D

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak »

i seriously doubt that, coz if just find 2 convex hulls and check if any point in another convex hull, even the second sample input won't output NO. so you mean the sample output is wrong? or there's more trick?

ahanys
New poster
Posts: 24
Joined: Mon Nov 19, 2001 2:00 am
Location: N/A
Contact:

TESTING

Post by ahanys »

YOU must test if every point of first convex hull is in second an if any point of second convex hull is in the first. If any THEN PRINT NO!

ntrhieu
New poster
Posts: 21
Joined: Mon Oct 22, 2001 2:00 am

Post by ntrhieu »

actually, from what I am doing, there are two steps:
( Assume the deviding line cannot contain any vertex)
1) Find convex hulls of two sets of points.
2) Check if one point of a convex STRICTLY INSIDE the other convex. If there is, the answer is no, otherwise, go to step 3.
3) If there is at least one intersection point between two edges (segments not lines) of the hulls, then no deviding line exists.
It's done.

However, if we assume that the deviding line can contain vertices of both sets.
Then, on step 3, we find all intersection points. Make them unique.
If there is only one point -> YES.
If they are co-linear ( on the same line), then check if the line is the deviding line we're looking for (it's easy to check); else (there are three or more points that are not co-linear) the answer is NO.

I have coded this algorithms, and tried both assumptions, but still got WA.
What was wrong with my algorithms ? Please point out for me.

Thanks
Hieu Nguyen

ntrhieu
New poster
Posts: 21
Joined: Mon Oct 22, 2001 2:00 am

10256 - The Great Divide

Post by ntrhieu »

It has lead me to strongly believe that there was something wrong with either the judge's input or output in this problem. As you may have noticed, there were only 3 people solved this out of more than 200 submissions. I have checked with one of them, and he said that there was actually something wrong with the judge's output, the judge's solution did not handle the special cases of the problem correctly. He had to make his solution from right -> wrong for some special cases to get it accepted after 30 tries (for example, he said, if the size of either sets is <= 1, then the solution is Yes, which is obviously wrong, when one point is strictly inside a convex hull of the other set of points)
Please, if you can, check back with the judge's solution/input/output carefully.

Thanks
Hieu Nguyen

Carlos
System administrator
Posts: 1286
Joined: Sat Oct 13, 2001 2:00 am
Location: Valladolid, Spain
Contact:

Mail me.

Post by Carlos »

I'm one of the judge's administrator. Please, mail me at:

problemset@acm.uva.es

if anyone wants to help me.
Thanks.
Carlos.

Carlos
System administrator
Posts: 1286
Joined: Sat Oct 13, 2001 2:00 am
Location: Valladolid, Spain
Contact:

and...

Post by Carlos »

And attach your rejected problem (the one you think is right)
Thanks again.

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:

Re: To Judges / Admins: prob 10256 - The Great Divide

Post by ftomi »

ntrhieu wrote:(for example, he said, if the size of either sets is <= 1, then the solution is Yes, which is obviously wrong
why? I think it's right.
Now my soulution rejudged to wrong. :evil: Is this the only modification?

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:

Post by ftomi »

The two chiefs have decided to divide the village into two parts by digging a straight ditch through the middle of the village so that the houses of the supporters of Majestix lie on one part and those of the followers of Cleverdix lie on the other.
If there is no supporters for Majestix, then exist a good line far from the village: the houses of the supporters of Majestix lie on one part (however there is no house) and the followers of Cleverdix lie on the other. What's the problem?

ntrhieu
New poster
Posts: 21
Joined: Mon Oct 22, 2001 2:00 am

Post by ntrhieu »

Hi,
I think you have a mistakehere. "<=1", NOT "<1", of course it was wrong if the set of points of supporters of Majestix consist of a polygon that contains the 1 point of the supporter of Cleverdix.
Hieu Nguyen

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:

Post by ftomi »

Thank you! (AC again)

Post Reply

Return to “Volume 102 (10200-10299)”