This page is still under construction.

Parts of this page are still being built. What you see may change.

Property Lines

Interview

Time limit1sMemory limit128 MB

Summary
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 WW, a real number HH, and an integer NN, in that order. The city is a rectangle in the xyxy plane with length WW along xx and length HH along yy, and its lower left corner sits at (0,0)(0, 0). NN is the number of residents who claimed land.

Each of the next NN lines holds one claim in the format X Y LX LY. (X,Y)(X, Y) is the lower left corner of the claimed rectangle, LXLX is its length along xx, and LYLY is its length along yy.

The input ends at a line whose WW, HH, and NN are 0 0 0. That line is not a test case.

0<W≤10000 < W \le 1000, 0<H≤10000 < H \le 1000, 0≤N≤1000 \le N \le 100, 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

dd is the area claimed by two or more people, cc is the area claimed by one or more people, and uu 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 0.010.01, so no value lands on a rounding boundary.

Examples2

  1. Example 1

    Input
    4.0 4.0 2
    1.0 1.0 2.0 2.0
    2.0 1.0 2.0 2.0
    0 0 0
    
    Expected output
    Disputed: 2.000
    Claimed: 6.000
    Unclaimed: 10.000
    
  2. Example 2

    Input
    2.0 2.0 1
    0.0 0.0 1.0 1.0
    3.0 3.0 2
    0.0 0.0 3.0 1.0
    0.0 0.0 1.0 3.0
    0 0 0
    
    Expected output
    Disputed: 0.000
    Claimed: 1.000
    Unclaimed: 3.000
    Disputed: 1.000
    Claimed: 5.000
    Unclaimed: 4.000