### 10321 - Polygon Intersection

Posted:

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

Page **1** of **2**

Posted: **Thu Jul 04, 2002 3:55 am**

Do I need to do convex hull in this problem?

Posted: **Thu Jul 04, 2002 7:26 pm**

i believe not

Posted: **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 ?

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

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.

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

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 ?

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

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

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

Posted: **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.

That's why I posted here to seek help.

Posted: **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 ).

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

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

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

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.

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

Posted: **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...

Can anyone help me?!?

THANK YOU!!

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

Posted: **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:

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

- 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

Posted: **Tue Jul 19, 2005 9:09 am**

Hi all,

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

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

Posted: **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.

Input:-
Output :-

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

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