Page 1 of 2

10321 - Polygon Intersection

Posted: Thu Jul 04, 2002 3:55 am
by dh3014
Do I need to do convex hull in this problem?

Posted: Thu Jul 04, 2002 7:26 pm
by wyvmak
i believe not

problem ambiguity

Posted: Sun Jul 07, 2002 10:28 pm
by ntrhieu
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 print only only one point or two points ?

3. What is "lexicographically ordered" in this problem ?

Posted: Mon Jul 08, 2002 8:09 am
by wyvmak
1. i think it's just normal rounding method, <4, drop it, >=5, one unit up. 0.995 will be 1.00. btw, your -0.5 will just be -0.50.
2. i think two points, if rounding is the same, still output twice.
3. sort by x coordinates, if same x, then sort by y.

Posted: Mon Jul 08, 2002 8:59 am
by ntrhieu
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 ?

Posted: Tue Jul 09, 2002 5:28 pm
by wyvmak
well, maybe i'm naive (that's why i'm just an amateur). i never consider such things (that's why it's so hard for me to understand or get AC in difficult questions). anyway,

if -0.005, i'd output -0.01if the two polygons touch, consider that is an intersection point.
btw, did you try problem 137? the questions alike

dh3014

Posted: Thu Jul 11, 2002 5:16 am
by dh3014
I've solved acm137 already, but not this one...
That's why I posted here to seek help.

Posted: Thu Jul 11, 2002 6:27 am
by ntrhieu
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 simpler than prob 137.
I think the prob is poorly defined, no definition of what's intersection point in special cases. Such probs just waste people's time and not fun at all (except to the author :) ).

Posted: Sat Jul 13, 2002 12:37 am
by Adrian Kuegel
The polygons in the input are convex. You have to print the intersection points (that means also points which are inside the other polygon) sorted by x, then by y value. I think it was due to my algorithm, but I had to reduce the set of intersection points so that it contained no duplicates to get Accepted.

Posted: Sat Jul 13, 2002 1:34 am
by ntrhieu
Thanks for the help, I didn't expect inside points to be intersection points. Now I got AC.

Posted: Sat Jul 13, 2002 2:27 am
by Picard
it was not clear to me either :x
"intersecting points of the input polygons" -> inside points are not intersecting points (for me), they are only points of the intersection area. an intersecting point is obtained by the intersection of two lines.
btw not all sample input polygons have clockwise traversal order.

10321 This problem is making me crazy!!! (polygon intersect)

Posted: Mon May 24, 2004 9:44 am
by setack
Plz, can anyone tell me what's the real description for this problem?!?!?
I consider as a intersecting points de intersections between the segments of the two polygons and the vertexs which are inside the other polygon (in other words, the polygon intersection of the 2 polygons).
Is it consider as an intersecting point if 2 polygons have a common vertex?
And so on with hundreds of questions... :cry:

Can anyone help me?!?

THANK YOU!!

Please Help

Posted: Wed Nov 24, 2004 4:57 pm
by Moha
can anybody who accepted test this testcases(although they are incorrect because they are`nt in clockwise order as indicated in problem statement)
input:
  • 6
    77 86
    93 15
    86 35
    49 92
    62 21
    90 27

    22
    26 63
    26 40
    36 72
    68 11
    29 67
    30 82
    23 62
    35 67
    2 29
    58 22
    67 69
    56 93
    42 11
    73 29
    19 21
    37 84
    24 98
    70 15
    26 13
    80 91
    73 56
    70 62

    19
    5 81
    84 25
    36 27
    46 5
    13 29
    24 57
    82 95
    14 45
    34 67
    43 64
    87 50
    76 8
    88 78
    3 84
    54 51
    32 99
    76 60
    39 68
    26 12

    9
    39 94
    70 95
    78 34
    1 67
    2 97
    92 17
    56 52
    80 1
    41 86

    8
    44 89
    40 19
    31 29
    97 17
    81 71
    9 75
    67 27
    97 56

    16
    65 86
    83 6
    24 19
    71 28
    29 32
    19 3
    68 70
    15 8
    49 40
    23 96
    45 18
    51 46
    55 21
    88 79
    28 64
    50 41

    16
    34 0
    24 64
    87 14
    43 56
    27 91
    59 65
    32 36
    37 51
    75 28
    74 7
    58 21
    29 95
    35 37
    18 93
    43 28
    28 11

    12
    4 76
    63 43
    38 13
    40 6
    18 4
    88 28
    17 69
    96 17
    43 24
    83 70
    99 90
    25 72

    7
    5 90
    54 39
    69 86
    42 82
    97 64
    55 7
    48 4

    14
    28 22
    43 99
    68 46
    22 40
    10 11
    1 5
    30 61
    5 78
    36 20
    26 44
    65 22
    16 8
    58 82
    37 24
    0
my output is:
  • 18
    62.68 21.15
    54.43 62.35
    55.63 55.80
    59.69 33.60
    60.86 27.20
    61.73 22.46
    52.53 72.70
    59.95 32.19
    61.60 23.21
    68.45 62.04
    64.34 68.37
    54.41 83.67
    66.18 21.90
    66.30 65.35
    73.00 29.00
    78.05 81.24
    77.00 86.00
    78.06 81.30
    44
    53.08 51.59
    76.25 8.96
    76.29 9.09
    76.19 9.10
    76.21 9.25
    24.75 56.82
    28.12 55.38
    24.13 57.09
    35.35 52.28
    52.48 60.98
    68.40 25.65
    83.76 25.01
    82.95 25.04
    61.75 40.77
    61.05 41.27
    83.16 25.60
    68.70 25.64
    80.93 26.84
    79.45 28.15
    81.13 27.57
    79.06 28.50
    79.61 29.05
    61.06 41.26
    75.42 53.69
    74.55 60.31
    74.40 61.41
    17.80 82.96
    3.00 84.00
    10.50 62.93
    34.00 67.00
    38.25 64.78
    39.45 63.71
    50.39 65.54
    36.80 66.07
    37.24 65.67
    48.26 70.19
    47.30 72.27
    72.08 79.12
    5.00 81.00
    39.39 92.45
    43.22 81.16
    41.00 86.00
    70.95 87.76
    71.06 86.95
    54
    32.00 27.89
    32.69 28.69
    40.18 22.10
    28.00 64.00
    29.24 73.88
    37.65 21.61
    34.87 24.70
    33.89 25.78
    36.29 28.04
    37.19 27.87
    46.74 26.14
    31.00 29.00
    34.99 53.49
    33.38 73.65
    40.00 19.00
    56.87 24.30
    42.49 26.91
    54.20 24.78
    79.82 20.12
    54.40 24.75
    65.11 28.56
    66.77 27.19
    67.00 27.00
    67.30 27.29
    68.30 28.26
    71.00 28.00
    40.68 30.89
    61.16 31.83
    40.76 32.24
    40.79 32.79
    40.79 32.91
    76.26 35.95
    41.12 38.55
    52.06 39.36
    47.57 43.08
    46.06 44.33
    48.03 42.70
    49.00 40.00
    49.68 41.33
    49.95 41.11
    41.75 49.63
    42.05 54.96
    42.78 67.70
    50.00 41.00
    50.02 41.05
    80.69 66.15
    68.22 71.71
    60.55 72.14
    60.38 72.15
    62.22 77.66
    68.06 74.02
    67.64 74.28
    81.84 68.17
    81.00 71.00
    48
    24.34 72.13
    27.35 62.18
    27.05 63.20
    27.08 63.09
    32.59 9.00
    33.16 5.38
    25.00 72.00
    25.98 72.24
    31.17 5.20
    29.64 7.99
    30.15 61.41
    30.17 61.36
    32.76 58.62
    32.62 59.98
    30.70 59.98
    31.22 73.51
    32.62 59.99
    57.58 22.07
    46.90 49.32
    53.74 31.88
    60.70 18.64
    74.61 19.83
    52.53 34.96
    45.35 50.34
    45.68 52.44
    45.55 52.76
    46.74 51.83
    46.90 52.00
    43.00 56.00
    34.62 74.34
    36.88 74.89
    44.54 76.75
    81.91 18.86
    48.34 50.90
    47.59 51.62
    55.82 38.74
    56.31 39.31
    56.88 42.75
    80.67 19.02
    58.00 21.00
    74.78 23.47
    74.98 23.54
    76.47 24.05
    58.01 37.01
    58.71 37.86
    58.21 41.49
    59.00 65.00
    60.17 39.61
    23
    42.25 15.50
    14.09 71.82
    31.08 37.83
    28.79 42.43
    55.72 44.40
    24.66 50.68
    31.95 36.10
    65.00 22.00
    29.51 40.98
    35.14 58.63
    30.00 61.00
    37.42 25.16
    45.60 47.75
    41.17 52.35
    42.00 82.00
    49.58 43.60
    50.43 83.25
    60.98 60.88
    68.00 46.00
    56.30 77.32
    55.49 77.58
    52.67 78.51
    58.00 82.00
Thanks.

10321

Posted: Tue Jul 19, 2005 9:09 am
by Chok
Hi all,
Please give me some input/output. I'm getting WA. Thankx in advance.

Re

Posted: Mon Aug 01, 2005 6:31 pm
by Raj Ariyan
Hi Chok,
Sorry 4 very late reply. Here is some i/o(also included the problem i/o) . Verify it. Good Luck. :D

Input:-

Code: Select all

5
3 0
3 4
1 1
-2 2
-2 0
5
3 1
4 2
-2 5
-3 1
0 2
4
3 0
5 2
3 3
1 2
4
3 1
5 3
3 5
1 3
3 
0 0 
0 2 
2 2
4 
5 5 
5 10 
10 10 
10 5
4 
1 1 
5 1 
5 5 
1 5
4 
3 0 
6 3 
3 6 
0 3
2
Output :-

Code: Select all

7
-2.00 1.33
-2.00 2.00
-1.00 1.67
1.36 1.55
2.25 2.88
3.00 1.00
3.00 2.50
4
1.67 2.33
3.00 1.00
3.00 3.00
4.33 2.33
0
8
1.00 2.00
1.00 4.00
2.00 1.00
2.00 5.00
4.00 1.00
4.00 5.00
5.00 2.00
5.00 4.00