10256  The Great Divide
Moderator: Board moderators
10256  The Great Divide
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
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

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
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)
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
same question
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?
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?
Solution to this problem!!!!
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.
TESTING
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!
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 colinear ( 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 colinear) 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
( 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 colinear ( 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 colinear) 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
10256  The Great Divide
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
Please, if you can, check back with the judge's solution/input/output carefully.
Thanks
Hieu Nguyen

 System administrator
 Posts: 1286
 Joined: Sat Oct 13, 2001 2:00 am
 Location: Valladolid, Spain
 Contact:
Mail me.
I'm one of the judge's administrator. Please, mail me at:
problemset@acm.uva.es
if anyone wants to help me.
Thanks.
Carlos.
problemset@acm.uva.es
if anyone wants to help me.
Thanks.
Carlos.
Re: To Judges / Admins: prob 10256  The Great Divide
why? I think it's right.ntrhieu wrote:(for example, he said, if the size of either sets is <= 1, then the solution is Yes, which is obviously wrong
Now my soulution rejudged to wrong. Is this the only modification?
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?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.