IOI 1998 day2 1- 벽에 붙은 그림(Picture) > 문제은행 : 정보올림피아드&알고리즘




1631 : 벽에 붙은 그림(Picture)

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
13 회   
시도횟수
30 회   

문제

직사각형 모양의 포스터, 사진, 그리고 여러 그림들이 한 벽에 붙어 있다. 

방향은 모두 가로 아니면 세로이다. 각각의 직사각형들은 다른 직사각형의 일부나 전부를 덮어 가릴 수 있다. 

모든 직사각형들을 합했을 때의 실제 둘레를 최종 경계선이라고 부르겠다. 

이때 최종 경계선 길이를 계산하는 프로그램을 작성하라.

 

이해를 위해 예제로 7개의 임의의 직사각형을 아래 왼쪽 그림에 도시하였다.

 

 


 

 

직사각형의 최종 경계선은 위쪽 오른쪽에 그려진 다각형의 둘레와 같다. 

모든 직사각형의 좌표는 정수형이다.

 

<제약조건>
직사각형의 개수는 0개 이상 5000개 이하이다. 

좌표의 범위는 -10000에서 10000이나, 넓이는 모두 양수가 나온다. 

결과의 값은 231보다 작은 수가 출력된다.

 


입력형식

입력파일의 첫 줄에는 벽에 붙어 있는 직사각형 그림의 개수가 적혀 있다.

그리고 다음 줄부터는 사각형의 좌표가 들어 있다.
(x1 y1 x2 y2식으로) 값들은 모두 좌표평면의 왼쪽, 아래쪽에 있는 점 좌표가 먼저 나온다. 아래의 입력 예제는 위에서 제시한 사각형들의 좌표와 일치한다.


출력형식

출력 파일은 파일에는 입력 자료를 읽어 계산한 경계선의 길이가 자연수로 적혀야 한다.


입력 예

7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16

출력 예

228


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP