Problem # 223

[chemically_yours]

i want to solve problem number 223 "Classifying lots in Subdivisions" but im unable to make any logic to solve it... so plz i require some basic hint, directions and techniques to solve this problem...plz

[sclo]

The idea isn't complicated. For each vertex, keep a list of its neighbors in sorted angular order, then we can traverse the list of all edges in linear time, and the list of neighbor will tell us which edge to visit next. Using this method, for each region, we can traverse the edges corresponding to its boundary. There is a simple way to detect the region corresponding to the region outside bounding rectangle.

[gt1404]

It seems every time I attempt a harder puzzle I always get WA even though I'm convinced my algorithm is correct. Can anyone clarify the output specifications for this problem, the instructions are vague and the formatting is the likely culprit.

-gt


INPUT:

Code: Select all

4
0 0 1 0
0 0 0 1
0 1 1 1
1 0 1 1

8
0 0 2 0
2 0 2 2
2 2 0 2
0 0 0 2
0 0 1 1
2 0 1 1
1 1 2 2
1 1 0 2

12
10 41 15 41
15 41 20 41
10 36 15 36
15 36 17 36
10 31 15 31
15 31 20 31
10 41 10 36
10 36 10 31
15 41 17 34
17 34 17 36
15 36 15 31
20 41 20 31

27
10 22 19 22
19 22 23 22
23 22 28 22
28 22 37 22
10 16 16 16
17 16 23 16
23 16 24 16
24 15 28 15
28 15 31 15
10 10 17 10
17 10 24 10
24 10 31 10
31 10 37 10
10 22 10 16
10 16 10 10
17 18 17 16
17 16 17 10
24 16 24 15
24 15 24 10
23 22 23 16
28 22 28 15
31 15 31 10
37 22 37 17
37 17 37 10
16 16 17 18
17 18 19 22
31 15 37 17

10
0 0 1 0
1 0 2 0
0 0 0 1
0 1 0 2
0 2 1 2
1 2 2 2
2 0 2 1
2 1 2 2
0 0 1 1
1 1 2 0

8
0 0 1 0
1 0 2 0
0 0 0 1
0 1 0 2
0 2 1 2
1 2 2 2
2 0 2 1
2 1 2 2

9
0 0 1 0
1 0 2 0
2 0 3 0
3 0 3 2
3 2 0 2
0 2 0 0
1 0 1 1
1 1 2 1
2 1 2 0

16
0 0 1 0
1 0 4 0
4 0 4 2
4 2 4 4
4 4 0 4
0 4 0 0
1 0 1 1
1 1 3 1
3 1 4 0
0 4 1 2
1 2 1 1
3 1 3 2
4 4 2 3
2 3 2 2
2 2 3 2
3 2 4 2
0


OUTPUT:

Code: Select all

Case 1
Number of lots with perimeter consisting of 4 surveyor's lines = 1
Total number of lots = 1

Case 2
Number of lots with perimeter consisting of 3 surveyor's lines = 4
Total number of lots = 4

Case 3
Number of lots with perimeter consisting of 4 surveyor's lines = 1
Number of lots with perimeter consisting of 6 surveyor's lines = 1
Number of lots with perimeter consisting of 7 surveyor's lines = 1
Total number of lots = 3

Case 4
Number of lots with perimeter consisting of 4 surveyor's lines = 1
Number of lots with perimeter consisting of 5 surveyor's lines = 4
Number of lots with perimeter consisting of 6 surveyor's lines = 3
Total number of lots = 8

Case 5
Number of lots with perimeter consisting of 4 surveyor's lines = 1
Number of lots with perimeter consisting of 8 surveyor's lines = 1
Total number of lots = 2

Case 6
Number of lots with perimeter consisting of 8 surveyor's lines = 1
Total number of lots = 1

Case 7
Number of lots with perimeter consisting of 4 surveyor's lines = 1
Number of lots with perimeter consisting of 8 surveyor's lines = 1
Total number of lots = 2

Case 8
Number of lots with perimeter consisting of 4 surveyor's lines = 2
Number of lots with perimeter consisting of 5 surveyor's lines = 2
Number of lots with perimeter consisting of 8 surveyor's lines = 1
Total number of lots = 5



[brianfry713]

My AC code matches your I/O, don't print a newline at the end. Note that the 0 coordinates should not appear in your input, the spec says they are between 1 and 10000. I also noticed the first sample input in the spec is wrong. The point 17,34 should be 17,38 instead.