직사각형의 교차 영역

2003 가을학기 문제해결기법	문제 #6

아래 그림과 같이 네 변이 모두 x-축이나 y-축에 평행한 직사각형이 입력될 때, 입력되는 모든 직사각형이 교차하는 영역의 면적을 구하여 출력하는 프로그램을 작성하시오. 교차 영역이 없을 때 면적은 0이라고 간주한다.

직사각형을 나타내기 위해서 왼쪽 아래 꼭지점의 좌표와 오른쪽 위 꼭지점의 좌표가 주어지면 충분하다. 예를 들어 직사각형 R1은 왼쪽 아래 꼭지점의 좌표 (3.0, 6.0)과 오른쪽 위 꼭지점의 좌표 (6.0, 12.0)으로 나타낸다.

프로그램 이름은 rect.cpp, 프로그램 설명 파일 이름은 rect.hwp로 하고, 실행 시간은 1초를 초과할 수 없다. 부분 점수는 없다.

입력 형식

입력 파일의 이름은 input.txt이다. 첫 줄에 직사각형의 수 [eqn: n]이 입력된다. 둘째 줄부터 마지막 줄까지 한 줄에 직사각형이 하나씩 입력된다. 직사각형의 왼쪽 아래 꼭지점의 좌표가 [eqn: (x_1 , y_1 )]이고, 오른쪽 위 꼭지점의 좌표가 [eqn: (x_2 , y_2 )]라면 네 실수 [eqn: x_1 , y_1],[eqn: x_2 , y_2]가 한 줄에 입력되며, 그들 사이에 빈칸이 하나 혹은 여럿 있다.

출력 형식

출력 파일의 이름은 output.txt이다. 첫째 줄에 입력되는 모든 사각형이 교차하는 영역의 면적을 출력한다.

입력과 출력의 예

입력(input.txt)

4

3.0 6.0 6.0 12.0

1 2 10 9

4 4 9 10

5 5 7 8

출력(output.txt)

2.0