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

likhan
New poster
Posts: 21
Joined: Tue Nov 06, 2001 2:00 am
Location: Kyliptix Solutions

Post 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
Last edited by likhan on Fri Nov 15, 2002 8:14 pm, edited 1 time in total.

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

Post 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).
Hieu Nguyen

likhan
New poster
Posts: 21
Joined: Tue Nov 06, 2001 2:00 am
Location: Kyliptix Solutions

Post by likhan »

Thanx ntrhieu got ac.

sunhong
New poster
Posts: 19
Joined: Sat Apr 12, 2003 6:13 pm
Location: China

10256-The great divide,WA

Post 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!

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post 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....
Jalal : AIUB SPARKS

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker »

:D got AC after 20+ submissions

simplified my approach, and it helped
Jalal : AIUB SPARKS

Piotr42
New poster
Posts: 4
Joined: Sun Dec 02, 2007 8:09 pm

10256 - time limit

Post 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

Post Reply

Return to “Volume 102 (10200-10299)”