## Search found 21 matches

Fri Nov 15, 2002 4:29 am
Forum: Volume 102 (10200-10299)
Topic: 10256 - The Great Divide
Replies: 21
Views: 7781
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, ...
Sat Jul 13, 2002 1:34 am
Forum: Volume 103 (10300-10399)
Topic: 10321 - Polygon Intersection
Replies: 17
Views: 7566
Thanks for the help, I didn't expect inside points to be intersection points. Now I got AC.
Thu Jul 11, 2002 6:27 am
Forum: Volume 103 (10300-10399)
Topic: 10321 - Polygon Intersection
Replies: 17
Views: 7566
I think prob 137 and this one are quite different problems. Since we're not sure if two polygons are convex in this problem (even though it unclearly mentioned something like that in the output description, it also said the two polygons are arbitrary at the beginning). In fact, i think this one is s...
Mon Jul 08, 2002 1:01 pm
Forum: Other words
Topic: graph theory question
Replies: 2
Views: 4402
thanks, it said O(n) to determine strongly connected components. Looks great
Mon Jul 08, 2002 9:07 am
Forum: Other words
Topic: graph theory question
Replies: 2
Views: 4402

### graph theory question

what is the best algorithms to find all strongly connected component of a graph ? I only know the trivial one in text book with time O(V * (E+v)) or O(V^3).

Thanks
Mon Jul 08, 2002 8:59 am
Forum: Volume 103 (10300-10399)
Topic: 10321 - Polygon Intersection
Replies: 17
Views: 7566
actually I wanted to ask if -0.005 should be rounded "up" to 0.00 or -0.01 as usual.
btw, i think all we need is to find any intersection points of the edges of two polygons. Why is it so hard to get AC ?
If one polygon "touches" the other (they have exactly one point in common), do they intersect ?
Sun Jul 07, 2002 10:28 pm
Forum: Volume 103 (10300-10399)
Topic: 10321 - Polygon Intersection
Replies: 17
Views: 7566

### problem ambiguity

Hi, for this problem, I have several questions, if someone can help me clarify them: 1. What did it mean by "round up" anyway ? What is the round up for these numbers: -0.5 0.5 0.3 -0.3 0.7 -0.7 2. If two intersection points are actually different but their rounded format are the same, should I prin...
Fri May 31, 2002 10:06 pm
Forum: Volume 1 (100-199)
Topic: 168 - Theseus and the Minotaur
Replies: 64
Views: 8745
Admins, what happened ? Now they put such a test that there is no passage from the Theseus to Minotaur (unless I read input incorrectly).
So, what's the output would be for that case ?
Fri May 31, 2002 3:50 pm
Forum: Volume 102 (10200-10299)
Topic: 10256 - The Great Divide
Replies: 21
Views: 7781
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.
Sat May 11, 2002 8:56 am
Forum: Volume 102 (10200-10299)
Topic: 10256 - The Great Divide
Replies: 21
Views: 7781

### 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 wr...
Tue May 07, 2002 5:20 am
Forum: Volume 102 (10200-10299)
Topic: 10256 - The Great Divide
Replies: 21
Views: 7781
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 o...
Thu Apr 18, 2002 5:59 pm
Forum: Volume 102 (10200-10299)
Topic: 10256 - The Great Divide
Replies: 21
Views: 7781
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 divi...
Thu Apr 18, 2002 5:30 pm
Forum: Volume 102 (10200-10299)
Topic: 10256 - The Great Divide
Replies: 21
Views: 7781

### 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 diffe...
Sun Apr 14, 2002 8:13 pm
Forum: Volume 1 (100-199)
Topic: 173 - Network Wars
Replies: 29
Views: 3209
Oops, I missent the msg to some place, it didn't show up in the forum. The second input I gave you was B:ACD.B D (with no space after .) not B:ACD. B D The problem is when you read scanf("%s %c %c, &, &, &) it wil read everything into your first string, and then D to the first %c, and the second %c ...
Sun Apr 14, 2002 7:23 pm
Forum: Volume 1 (100-199)
Topic: 173 - Network Wars
Replies: 29
Views: 3209
Here is the output for your input of my AC program: Paskill trapped in node D Lisper trapped in node F Both annihilated in node E Lisper trapped in node E Both annihilated in node A Paskill trapped in node A Both annihilated in node Paskill trapped in node B Both annihilated in node Both annihilated...