Page 2 of 2
Posted: Fri Nov 15, 2002 1:51 am
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
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
Thanx ntrhieu got ac.
10256-The great divide,WA
Posted: Fri Apr 16, 2004 7:14 am
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?
Posted: Fri Jul 14, 2006 10:15 am
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
got AC after 20+ submissions
simplified my approach, and it helped
10256 - time limit
Posted: Sun Dec 23, 2007 5:56 pm
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?