10321 - Polygon Intersection

[dh3014]

Do I need to do convex hull in this problem?

[wyvmak]

i believe not

[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 ?

[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]

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 ?

[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]

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

[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 ).

[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]

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

[Picard]

it was not clear to me either
"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]

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

Can anyone help me?!?

THANK YOU!!

[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]

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

[Raj Ariyan]

Hi Chok,
Sorry 4 very late reply. Here is some i/o(also included the problem i/o) . Verify it. Good Luck.

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