10256 - The Great Divide

[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

[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]

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)

[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]

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.

[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]

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]

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

[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

[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]

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

[ftomi]

(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. Is this the only modification?

[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]

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.

[ftomi]

Thank you! (AC again)