## Problem # 223

Moderator: Board moderators

### Problem # 223

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
chemically_yours
New poster

Posts: 1
Joined: Wed May 19, 2004 5:23 pm
Location: Karachi, Pakistan

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

Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm

### Re: Problem # 223

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
`40 0 1 00 0 0 10 1 1 11 0 1 180 0 2 02 0 2 22 2 0 20 0 0 20 0 1 12 0 1 11 1 2 21 1 0 21210 41 15 4115 41 20 4110 36 15 3615 36 17 3610 31 15 3115 31 20 3110 41 10 3610 36 10 3115 41 17 3417 34 17 3615 36 15 3120 41 20 312710 22 19 2219 22 23 2223 22 28 2228 22 37 2210 16 16 1617 16 23 1623 16 24 1624 15 28 1528 15 31 1510 10 17 1017 10 24 1024 10 31 1031 10 37 1010 22 10 1610 16 10 1017 18 17 1617 16 17 1024 16 24 1524 15 24 1023 22 23 1628 22 28 1531 15 31 1037 22 37 1737 17 37 1016 16 17 1817 18 19 2231 15 37 17100 0 1 01 0 2 00 0 0 10 1 0 20 2 1 21 2 2 22 0 2 12 1 2 20 0 1 11 1 2 080 0 1 01 0 2 00 0 0 10 1 0 20 2 1 21 2 2 22 0 2 12 1 2 290 0 1 01 0 2 02 0 3 03 0 3 23 2 0 20 2 0 01 0 1 11 1 2 12 1 2 0160 0 1 01 0 4 04 0 4 24 2 4 44 4 0 40 4 0 01 0 1 11 1 3 13 1 4 00 4 1 21 2 1 13 1 3 24 4 2 32 3 2 22 2 3 23 2 4 20`

OUTPUT:
Code: Select all
`Case 1Number of lots with perimeter consisting of 4 surveyor's lines = 1Total number of lots = 1Case 2Number of lots with perimeter consisting of 3 surveyor's lines = 4Total number of lots = 4Case 3Number of lots with perimeter consisting of 4 surveyor's lines = 1Number of lots with perimeter consisting of 6 surveyor's lines = 1Number of lots with perimeter consisting of 7 surveyor's lines = 1Total number of lots = 3Case 4Number of lots with perimeter consisting of 4 surveyor's lines = 1Number of lots with perimeter consisting of 5 surveyor's lines = 4Number of lots with perimeter consisting of 6 surveyor's lines = 3Total number of lots = 8Case 5Number of lots with perimeter consisting of 4 surveyor's lines = 1Number of lots with perimeter consisting of 8 surveyor's lines = 1Total number of lots = 2Case 6Number of lots with perimeter consisting of 8 surveyor's lines = 1Total number of lots = 1Case 7Number of lots with perimeter consisting of 4 surveyor's lines = 1Number of lots with perimeter consisting of 8 surveyor's lines = 1Total number of lots = 2Case 8Number of lots with perimeter consisting of 4 surveyor's lines = 2Number of lots with perimeter consisting of 5 surveyor's lines = 2Number of lots with perimeter consisting of 8 surveyor's lines = 1Total number of lots = 5`
gt1404
New poster

Posts: 6
Joined: Sat Dec 26, 2009 10:16 am

### Re: Problem # 223

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

Posts: 1755
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA