Security Cameras

Strangely enough, there's been a break-in at the company headquarters!
Unfortunately, the lack of security cameras in the building means that the criminal(s?) will escape scot-free.

To prevent such a thing from happening again, the company has decided to purchase some security cameras.
To simplify things a bit, we'll assume the building is very simple - the various passages in the company can only go north/south or east/west.
Now, these cameras contain mirrors that allow them to have a fairly good field of view.
Because of distortion and other factors, though, they can only see "straight" (see diagram).
The company would like to place cameras so that each hallway is completely covered by one (or more) cameras.
These cameras are expensive, of course, and so you'd like to minimize the number of cameras required.

Input

N ≤ 100, the number of hallways.
For each hallway, 1 line:
4 integers x1, y1, x2, y2, representing the start and end locations of the hallway respectively.
Assume the company floor is a 2D plane with (0,0) being the southwest corner and (10000,10000) the northeast corner.
Each hallway will either have (x1 == x2) or (y1 == y2) (not both!).
Parallel hallways will never overlap.

Output

The minimum number of cameras required.

Sample Input

6
1 4 7 4
2 2 2 4
2 2 6 2
6 1 6 6
5 1 6 1
3 6 5 6

Sample Output

4

Diagram

By putting cameras in the locations, uh, shown, every building location is covered.

All Submissions
Best Solutions

Point Value: 20
Time Limit: 1.00s
Memory Limit: 16M
Added: Feb 15, 2009
Author: hansonw1

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)