Property Lines
InterviewTime limit1sMemory limit128 MB
Given up to 100 claimed rectangles inside a W by H city, compute the area claimed twice or more, at least once, and never.
- Level
Medium5 of 10
- Topics
- Geometry, Brute force, Sorting
- Solved
- No attempts yet
Problem
The city is a rectangle. Its property lines were so outdated that the mayor let every property owner redraw the boundary of his or her own land. There is one condition: every property has to be a rectangle.
That produced a pile of conflicting claims. The city now needs to know how much land is disputed and how much land nobody claimed.
Compute the area claimed by two or more owners and the area claimed by no one. Nobody claims land outside the city.
Input
The input holds several test cases.
The first line of each test case has a real number , a real number , and an integer , in that order. The city is a rectangle in the plane with length along and length along , and its lower left corner sits at . is the number of residents who claimed land.
Each of the next lines holds one claim in the format X Y LX LY. is the lower left corner of the claimed rectangle, is its length along , and is its length along .
The input ends at a line whose , , and are 0 0 0. That line is not a test case.
, , , and there are at most 20 test cases. Every real number is given with at most one digit after the decimal point. Every claimed rectangle lies inside the city.
Output
Print three lines for each test case.
Disputed: d
Claimed: c
Unclaimed: u
is the area claimed by two or more people, is the area claimed by one or more people, and is the area nobody claimed. Print all three with exactly three digits after the decimal point and no comma grouping.
The constraints keep every answer a multiple of , so no value lands on a rounding boundary.