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 »

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 »

i believe not

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

problem ambiguity

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

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

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

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

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

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

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

dh3014

Post by dh3014 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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)”