2001년 가을학기 문제해결기법 - 문제 11

게시판의 포스터

직사각형 모양의 게시판에 크기가 다양한 직사각형 모양의 포스터가 붙어있다. 포스터들은 다른 포스터에 의해서 일부 혹은 전부가 가려질 수 있다. 문제는 포스터들의 합집합이 이루는 다각형들의 둘레 길이의 합을 구하는 것이다.

게시판과 포스터의 위치를 말하기 위해서 이들이 x,y-평면에 놓여있다고 가정한다. 그리고 게시판과 포스터의 변은 모두 x-축이나 y-축에 평행하다고 가정한다. 그리고 게시판이나 포스터를 나타내는 직사각형을 나타내기 위해서 왼쪽 아래 꼭지점과 오른쪽 위 꼭지점의 좌표가 주어진다.

모든 포스터는 게시판 안에 붙어 있다고 가정한다. 포스터들의 합집합이 이루는 다각형의 변은 모두 x-축이나 y-축에 평행한 직교 다각형이며 내부에 구멍(hole)이 있을 수 있음에 유의한다. 구멍이 있는 다각형의 둘레의 길이는 당연히 구멍의 둘레의 길이를 포함한다.

아래 그림에 7개의 포스터가 게시판에 붙어 있는 예가 있다. 포스터의 합집합이 이루는 다각형은 2개이고, 하나는 구멍이 있는 다각형이며 다른 하나는 구멍이 없는 다각형이다.

프로그램명은 poster.cpp(poster.c)라고 하고 실행 파일명은 poster.exe로 한다. 프로그램의 실행 시간은 5초를 초과할 수 없다.

입력 형식

입력 파일의 이름은 INPUT.TXT이다. 첫째 줄에 게시판의 왼쪽아래 꼭지점과 오른쪽위 꼭지점의 좌표가 주어진다. 둘째 줄에 포스터의 수가 주어지고, 셋째 줄부터 마지막줄까지 한 줄에 한 포스트의 두 꼭지점의 좌표가 - 왼쪽아래 꼭지점과 오른쪽위 꼭지점 - 차례로 주어진다. 포스터의 수는 1000을 넘지 않고 게시판과 포스터의 좌표는 실수로 주어지며 0 이상 10000.0 이하라고 가정한다.

출력 형식

출력 파일의 이름은 OUTPUT.TXT이다. 첫째 줄에 포스터에 의해서 생성된 직교 다각형들의 둘레 길이의 합을 출력한다.

입력과 출력의 예

INPUT.TXT

0.0 0.0 100.0 100.0

7

2.0 7.0 8.0 10.0

1.0 3.0 4.0 8.0

2.0 2.0 10.0 5.0

6.0 4.0 9.0 9.0

7.0 6.0 8.0 8.0

12.0 5.0 13.0 10.0

11.0 8.0 14.0 11.0

OUTPUT.TXT

60.0