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

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

아틀란티스

면접 대비

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

요약
최대 100개의 축에 평행한 직사각형이 주어질 때, 합집합의 넓이를 구해 소수점 둘째 자리까지 출력한다.
난이도

보통10점 중 7점

유형
기하, 세그먼트 트리, 누적 합, 정렬
정답자
아직 제출이 없습니다

문제

전설의 섬 아틀란티스를 묘사한 고대 그리스 문헌이 여러 편 전해진다. 그중 일부에는 섬의 일부 지역을 그린 지도가 실려 있는데, 안타깝게도 지도마다 아틀란티스의 서로 다른 지역을 담고 있다. 당신의 친구 빌은 지도가 존재하는 전체 넓이를 알고 싶어 한다. 당신은 이 값을 계산하는 프로그램을 작성하기로 했다.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 지도의 개수를 나타내는 정수 nn (1≤n≤1001 \le n \le 100)이 적힌 줄로 시작한다. 이어지는 nn개의 줄은 각각 하나의 지도를 나타내며, 네 실수 x1x_1, y1y_1, x2x_2, y2y_2 (0≤x1<x2≤1000000 \le x_1 < x_2 \le 100000; 0≤y1<y2≤1000000 \le y_1 < y_2 \le 100000)로 이루어진다(정수가 아닐 수 있다). (x1,y1)(x_1, y_1)은 지도가 나타내는 직사각형 영역의 왼쪽 위 꼭짓점, (x2,y2)(x_2, y_2)는 오른쪽 아래 꼭짓점의 좌표이다.

입력의 끝은 00 하나만 적힌 줄로 표시되며, 이 줄은 처리하지 않는다.

출력

각 테스트 케이스마다 두 줄을 출력한다. 첫 번째 줄은 Test case #k이며, 여기서 kk는 테스트 케이스의 번호이다(11부터 시작). 두 번째 줄은 Total explored area: a이며, aa는 탐사된 전체 넓이, 즉 해당 테스트 케이스에 있는 모든 직사각형의 합집합의 넓이를 소수점 아래 정확히 두 자리까지 나타낸 값이다.

인접한 두 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

예제3

  1. 예제 1

    입력
    2
    10 10 20 20
    15 15 25 25.5
    0
    
    예상 출력
    Test case #1
    Total explored area: 180.00
    
  2. 예제 2

    입력
    1
    0 0 100 100
    0
    
    예상 출력
    Test case #1
    Total explored area: 10000.00
    
  3. 예제 3

    입력
    1
    0 0 5 5
    2
    0 0 10 10
    5 5 15 15
    0
    
    예상 출력
    Test case #1
    Total explored area: 25.00
    
    Test case #2
    Total explored area: 175.00