Page 2 of 2

Posted: Fri Nov 15, 2002 1:51 am
by likhan
Hello
I have tried everything, I have atleast submitted this probnlem a hundred times but still can't figure out anything.

what I did was
1)Created convex hulls of the supporters
2) if any point is less than 1 then yes
3) if both contains 1 point then yes
4) if ( one contains 1 point and the other 2 ) then checked whether that point is one the line if yes then no else yes
5) if ( one contains 1 point and the other more than 2 ) then checked whether that point is inside the convex hull if yes then no else yes
6) else intersected the lines if any one them did intersect then no else yes

Posted: Fri Nov 15, 2002 4:29 am
by ntrhieu
As I know, they have corrected input data, that's why you see many people got AC. About your solution to the prob, did you consider if 2 convex hulls are nested, or if their edges overlap (instead of intersect) ?
That's the only problem I can see, assuming that your code is correct. Oh, to be sure, if one supporter & one follower are at the same point, then -> NO (but I don't think they have that test).

Posted: Fri Nov 15, 2002 8:16 pm
by likhan
Thanx ntrhieu got ac.

10256-The great divide,WA

Posted: Fri Apr 16, 2004 7:14 am
by sunhong
:cry:
I think my method is right: First ,calculate the convex hull of the two
point sets. Then check if they intersect. And I take every special case
,such as one or two points into account. But still get WA!

Can anyone tell me where the trick is or give me some data to debug?
Thank you!

Posted: Fri Jul 14, 2006 10:15 am
by CodeMaker
Hi, i m getting a lot of wa

can anyone help?

well its seems like i have done all the things mentioned in the above posts.

-->
swap the sets if set1 has more elements than set2

if all the elements of the 2 sets are not distinct then result is no

if any set has 0 element result is yes

if both set has 1 element result is yes

if set1 has 1 elem and set2 has 2 then if the point in set1 is on lineSeg made of the 2 points of set2 then result is no otherwise yes

if set1 has 1 elem and set2 has more than 2 then make convex hull with set2 and check if the point of set1 is inside or on the convex hull, if so the result is no otherwise yes

if both the sets has more than 1 elem make 2 convex hull

if any of the hulls are linear then consider it as a single line and now check for intersection

if there is intersection then result is no otherwise check if any of the convex hull has a vertex inside the other convex hull, if so then result is no otherwise yes

--->

so as you can see, the only thing i can do now is to test some data sets

help me out plz, thanks....

Posted: Sat Jul 15, 2006 5:38 pm
by CodeMaker
:D got AC after 20+ submissions

simplified my approach, and it helped

10256 - time limit

Posted: Sun Dec 23, 2007 5:56 pm
by Piotr42
Hi
I've posted this problem in C++ and I've got AC in 2.050
then i posted the same source code in Pascal and I've got TLE and the run time was 3.000 - but the time limit for this problem was 8 sec
so is it a bug in the judge or where is the problem?
thx