아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

땅 경계선 다시 그리기

면접 대비

시간 제한1초메모리 제한128 MB

요약
W와 H 크기의 도시에 최대 100개의 직사각형 주장이 주어질 때 두 번 이상 겹친 면적, 한 번 이상 차지한 면적, 아무도 주장하지 않은 면적을 구합니다.
난이도

보통10점 중 5점

유형
기하, 완전 탐색, 정렬
정답자
아직 제출이 없습니다

문제

도시는 직사각형 모양이다. 땅의 경계가 너무 낡아서 시장은 토지 소유자가 각자 자기 땅의 경계를 다시 그리게 했다. 조건은 하나, 모든 땅은 직사각형이어야 한다.

그러자 서로 겹치는 주장이 쏟아졌다. 시는 지금 분쟁 중인 땅이 얼마나 되고, 아무도 주장하지 않은 땅이 얼마나 남았는지 알아야 한다.

두 명 이상이 주장한 땅의 넓이와 아무도 주장하지 않은 땅의 넓이를 구하라. 도시 밖의 땅을 주장하는 사람은 없다.

입력

입력은 여러 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에 실수 WW, 실수 HH, 정수 NN이 순서대로 주어진다. 도시는 xyxy 평면 위의 직사각형이고, xx 방향 길이가 WW, yy 방향 길이가 HH이며, 왼쪽 아래 꼭짓점은 (0,0)(0, 0)이다. NN은 땅을 주장한 주민 수다.

이어지는 NN개 줄에 주장이 하나씩 X Y LX LY 형식으로 주어진다. (X,Y)(X, Y)는 주장한 직사각형의 왼쪽 아래 꼭짓점이고, LXLX는 xx 방향 길이, LYLY는 yy 방향 길이다.

WW, HH, NN이 0 0 0인 줄이 나오면 입력이 끝난다. 이 줄은 테스트 케이스가 아니다.

0<W≤10000 < W \le 1000, 0<H≤10000 < H \le 1000, 0≤N≤1000 \le N \le 100이고, 테스트 케이스는 최대 20개다. 실수는 모두 소수점 아래 한 자리까지 주어진다. 주장한 직사각형은 모두 도시 안에 들어간다.

출력

각 테스트 케이스마다 세 줄을 출력한다.

Disputed: d
Claimed: c
Unclaimed: u

dd는 두 명 이상이 주장한 땅의 넓이, cc는 한 명 이상이 주장한 땅의 넓이, uu는 아무도 주장하지 않은 땅의 넓이다. 세 값 모두 소수점 아래 셋째 자리까지 출력하고, 천 단위 쉼표는 쓰지 않는다.

입력 조건상 세 값은 항상 0.010.01의 배수라서 반올림이 애매해지는 경우는 없다.

예제2

  1. 예제 1

    입력
    4.0 4.0 2
    1.0 1.0 2.0 2.0
    2.0 1.0 2.0 2.0
    0 0 0
    
    예상 출력
    Disputed: 2.000
    Claimed: 6.000
    Unclaimed: 10.000
    
  2. 예제 2

    입력
    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
    
    예상 출력
    Disputed: 0.000
    Claimed: 1.000
    Unclaimed: 3.000
    Disputed: 1.000
    Claimed: 5.000
    Unclaimed: 4.000