10321 - Polygon Intersection

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

dh3014
New poster
Posts: 24
Joined: Tue Mar 26, 2002 2:00 am
Location: Taiwan
Contact:

10321 - Polygon Intersection

Post by dh3014 » Thu Jul 04, 2002 3:55 am

Do I need to do convex hull in this problem?

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » Thu Jul 04, 2002 7:26 pm

i believe not

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

problem ambiguity

Post by ntrhieu » Sun Jul 07, 2002 10:28 pm

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 ?
Hieu Nguyen

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » Mon Jul 08, 2002 8:09 am

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.

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

Post by ntrhieu » Mon Jul 08, 2002 8:59 am

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 ?
Hieu Nguyen

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » Tue Jul 09, 2002 5:28 pm

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
New poster
Posts: 24
Joined: Tue Mar 26, 2002 2:00 am
Location: Taiwan
Contact:

dh3014

Post by dh3014 » Thu Jul 11, 2002 5:16 am

I've solved acm137 already, but not this one...
That's why I posted here to seek help.

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

Post by ntrhieu » Thu Jul 11, 2002 6:27 am

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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sat Jul 13, 2002 12:37 am

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.

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

Post by ntrhieu » Sat Jul 13, 2002 1:34 am

Thanks for the help, I didn't expect inside points to be intersection points. Now I got AC.
Hieu Nguyen

Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:

Post by Picard » Sat Jul 13, 2002 2:27 am

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.

setack
New poster
Posts: 2
Joined: Mon May 24, 2004 9:36 am

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

Post by setack » Mon May 24, 2004 9:44 am

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

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Please Help

Post by Moha » Wed Nov 24, 2004 4:57 pm

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.

Chok
New poster
Posts: 48
Joined: Mon Jun 27, 2005 4:18 pm
Location: Hong Kong

10321

Post by Chok » Tue Jul 19, 2005 9:09 am

Hi all,
Please give me some input/output. I'm getting WA. Thankx in advance.

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

Re

Post by Raj Ariyan » Mon Aug 01, 2005 6:31 pm

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
Some Love Stories Live Forever ....

Post Reply

Return to “Volume 103 (10300-10399)”