## 746 - Polygon Visibility

Moderator: Board moderators

vinicius
New poster
Posts: 1
Joined: Wed Feb 12, 2003 7:19 pm
Location: Brazil

### 746 - Polygon Visibility

The output specification for Polygon Visibility is WRONG!!!!
You should output a colon (:) after the instance name.
The sample output should be:

Code: Select all

Instance 1:
VERTICAL
10 20
20 20
20 10
0.000
Instance 2:
1.000
15 15
20 19
25 15
20 10
-1.000
Also, you should never output -0.000. Output 0.000 (without sign) instead.

Good Luck!

Vinicius Jos

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

### If any body get AC, please check my output below.

I just wrote a brute force, enumerated every pair of vertices of the two polygons and find the LEFTMOST and RIGHTMOST line segment, comparing by CROSS PRODUCT. I got WA but not TLE. Could any body who has got AC check my output below?

Input:

Code: Select all

3 3
3 2
5 3
5 1
1 2
2 3
2 1

4 3
3 4
4 5
4 1
3 2
2 3
1 2
1 4

4 4
2 5
6 5
6 4
4 3
8 4
13 6
12 4
10 1

4 4
2 2
2 6
4 6
6 1
9 4
13 4
12 1
10 1

4 3
4 6
5 5
6 2
5 2
8 5
11 5
8 3

4 5
4 3
5 3
6 1
1 1
10 3
11 5
12 6
13 1
10 1

4 4
2 4
3 4
4 3
1 3
12 6
13 5
13 3
10 1

4 3
3 4
2 6
5 4
6 1
9 2
12 4
12 1

4 3
1 3
1 4
2 6
3 1
10 6
13 3
10 3

3 3
3 6
5 4
1 3
11 6
12 5
12 2

4 3
1 5
5 5
6 3
4 3
8 3
12 2
8 2

4 3
1 3
2 6
5 4
1 1
8 5
10 5
8 2

10 15
27 2
1 6
1 86
5 101
92 101
97 99
99 89
101 72
101 2
71 1
110 3
107 6
103 30
104 100
122 101
186 101
196 100
201 93
203 53
202 26
201 17
200 12
199 9
195 1
120 1

13 10
2 13
1 73
1 74
2 87
12 101
37 101
93 100
96 97
101 88
101 5
100 3
70 1
4 1
136 4
110 16
104 90
153 101
159 101
180 99
202 54
186 24
180 16
167 1

12 13
36 2
1 6
1 64
2 91
8 96
18 100
25 101
86 101
101 95
101 4
92 1
58 1
104 7
103 66
103 93
105 98
112 100
126 101
148 101
175 100
202 96
203 63
203 11
201 1
115 1

12 4
37 4
15 13
10 16
4 35
2 47
3 92
53 98
77 95
100 87
101 21
100 18
49 1
103 88
164 96
179 81
172 20

14 14
2 5
1 57
1 83
6 96
11 99
14 100
23 101
83 101
92 99
101 92
101 29
98 6
96 1
28 1
119 3
116 4
110 10
104 28
103 62
107 96
110 100
139 101
165 101
198 100
203 75
203 15
198 2
134 2

11 11
3 4
2 34
1 81
1 98
2 100
90 101
99 101
101 81
101 4
95 1
30 1
105 3
103 43
107 98
120 101
148 101
175 98
203 92
203 40
201 17
200 7
181 1

12 13
23 4
9 10
1 16
3 99
85 98
87 95
98 57
99 22
99 4
87 3
60 2
49 2
107 2
103 11
103 81
104 98
107 100
127 101
196 101
202 97
203 96
203 5
183 2
171 1
115 1

17 15
10 3
3 12
1 68
1 73
3 85
14 98
55 99
86 96
99 88
101 67
100 43
94 14
91 6
90 4
86 2
38 1
33 1
106 3
104 4
103 9
103 73
104 86
105 98
111 99
148 101
203 101
203 43
200 21
197 3
195 2
186 1
114 1

12 14
34 2
4 4
1 28
1 99
15 101
58 101
82 100
100 99
101 74
100 44
99 23
97 1
106 25
103 53
103 88
105 93
142 101
190 97
202 94
203 65
201 26
195 6
194 5
189 2
185 1
112 1

13 17
3 3
1 24
1 82
2 101
79 101
100 98
101 53
101 26
98 12
96 3
95 2
50 1
9 1
126 3
112 7
108 21
105 51
104 67
104 93
114 98
135 101
180 101
197 100
202 99
203 95
203 28
202 18
199 4
190 1
151 1

0 0
Output:

Code: Select all

Instance 1:
1.000
3 2
-1.000
Instance 2:
1.000
4 5
4 1
-1.000
Instance 3:
0.333
4 3
2 5
6 5
-1.000
Instance 4:
1.000
6 1
2 2
2 6
4 6
-0.833
Instance 5:
1.500
6 2
5 2
4 6
-0.750
Instance 6:
0.833
6 1
1 1
4 3
5 3
-0.400
Instance 7:
0.375
4 3
1 3
2 4
3 4
-0.429
Instance 8:
0.500
6 1
3 4
2 6
-0.571
Instance 9:
0.714
3 1
1 3
1 4
2 6
-0.375
Instance 10:
0.333
5 4
1 3
3 6
-0.444
Instance 11:
0.000
4 3
1 5
5 5
-1.000
Instance 12:
0.571
1 1
1 3
2 6
-0.667
Instance 13:
32.667
101 2
71 1
27 2
1 6
1 86
5 101
92 101
97 99
99 89
101 72
-21.000
Instance 14:
28.333
101 5
100 3
70 1
4 1
2 13
1 73
1 74
2 87
12 101
37 101
93 100
96 97
101 88
-8.000
Instance 15:
44.500
101 4
92 1
58 1
36 2
1 6
1 64
2 91
8 96
18 100
25 101
86 101
101 95
-29.333
Instance 16:
33.500
101 21
100 18
49 1
37 4
15 13
10 16
4 35
2 47
3 92
53 98
77 95
100 87
-0.931
Instance 17:
16.500
101 29
98 6
96 1
28 1
2 5
1 57
1 83
6 96
11 99
14 100
23 101
83 101
92 99
101 92
-21.333
Instance 18:
19.500
101 4
95 1
30 1
3 4
2 34
1 81
1 98
2 100
90 101
99 101
101 81
-19.500
Instance 19:
19.250
99 4
87 3
60 2
49 2
23 4
9 10
1 16
3 99
85 98
87 95
98 57
-9.200
Instance 20:
11.000
100 43
94 14
91 6
90 4
86 2
38 1
33 1
10 3
3 12
1 68
1 73
3 85
14 98
55 99
86 96
99 88
101 67
-29.000
Instance 21:
16.250
99 23
97 1
34 2
4 4
1 28
1 99
15 101
58 101
82 100
100 99
-15.333
Instance 22:
22.333
101 26
98 12
96 3
95 2
50 1
9 1
3 3
1 24
1 82
2 101
79 101
100 98
-9.625
Last edited by ImLazy on Wed Sep 17, 2008 8:22 am, edited 1 time in total.
I stay home. Don't call me out.

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

### Re: 746 - Polygon Visibility

I've found where I was wrong and I get AC now. This input:

Code: Select all

3 4
20001 3
30001 4
30001 2
10001 4
10001 2
1 1
1 5
0 0
The output should be:

Code: Select all

Instance 1:
0.000
30001 4
30001 2
0.000
But my old program output:

Code: Select all

Instance 1:
0.000
30001 4
30001 2
-0.000
I stay home. Don't call me out.