시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 569 148 77 20.370%

문제

2차원 평면상에 N(0≤N≤5,000)개의 직사각형들이 주어졌을 때, 이 직사각형들의 합집합을 구하는 프로그램을 작성하시오.

예를 들어 왼쪽은 7개의 직사각형이 주어진 모습이고, 오른쪽 그림은 그 직사각형의 합집합을 구한 예이다. 이러한 합집합을 구하면 하나의 다각형이 나오는데, 이 다각형의 둘레의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 직사각형의 개수 N이 주어진다. 다음 N개의 줄에는 각 사각형의 정보를 나타내는 네 정수 x1, y1, x2, y2가 주어진다. 이는 사각형의 대각선으로 마주 보는 두 꼭짓점의 좌표가 (x1, y1), (x2, y2)라는 의미이다. 좌표의 범위는 -10,000이상 10,000이하로 한다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1

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

예제 출력 1

228
W3sicHJvYmxlbV9pZCI6IjIxODUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHVkNTY5XHVjOWQxXHVkNTY5IiwiZGVzY3JpcHRpb24iOiI8cD4yXHVjYzI4XHVjNmQwIFx1ZDNjOVx1YmE3NFx1YzBjMVx1YzVkMCBOKDAmbGU7TiZsZTs1LDAwMClcdWFjMWNcdWM3NTggXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHViNGU0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWI0ZTRcdWM3NTggXHVkNTY5XHVjOWQxXHVkNTY5XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIGhlaWdodD1cIjE2MVwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMDA4XC9yZWN0LlBOR1wiIHdpZHRoPVwiNTMzXCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQgXHVjNjdjXHVjYWJkXHVjNzQwIDdcdWFjMWNcdWM3NTggXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNCBcdWJhYThcdWMyYjVcdWM3NzRcdWFjZTAsIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVhZGY4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWQ1NjlcdWM5ZDFcdWQ1NjlcdWM3NDQgXHVhZDZjXHVkNTVjIFx1YzYwOFx1Yzc3NFx1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1ZDU2OVx1YzlkMVx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWJhNzQgXHVkNTU4XHViMDk4XHVjNzU4IFx1YjJlNFx1YWMwMVx1ZDYxNVx1Yzc3NCBcdWIwOThcdWM2MjRcdWIyOTRcdWIzNzAsIFx1Yzc3NCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NTggXHViNDU4XHViODA4XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHVjODE1XHViY2Y0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWIxMjQgXHVjODE1XHVjMjE4IHgxLCB5MSwgeDIsIHkyXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViMjk0IFx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWIzMDBcdWFjMDFcdWMxMjBcdWM3M2NcdWI4NWMgXHViOWM4XHVjOGZjIFx1YmNmNFx1YjI5NCBcdWI0NTAgXHVhZjJkXHVjOWQzXHVjODEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCAoeDEsIHkxKSwgKHgyLCB5MilcdWI3N2NcdWIyOTQgXHVjNzU4XHViYmY4XHVjNzc0XHViMmU0LiBcdWM4OGNcdWQ0NWNcdWM3NTggXHViYzk0XHVjNzA0XHViMjk0IC0xMCwwMDBcdWM3NzRcdWMwYzEgMTAsMDAwXHVjNzc0XHVkNTU4XHViODVjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjJmNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjE4NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBpY3R1cmUiLCJkZXNjcmlwdGlvbiI6IjxwPkEgbnVtYmVyIG9mIHJlY3Rhbmd1bGFyIHBvc3RlcnMsIHBob3RvZ3JhcGhzIGFuZCBvdGhlciBwaWN0dXJlcyBvZiB0aGUgc2FtZSBzaGFwZSBhcmUgcGFzdGVkIG9uIGEgd2FsbC4gVGhlaXIgc2lkZXMgYXJlIGFsbCB2ZXJ0aWNhbCBvciBob3Jpem9udGFsLiBFYWNoIHJlY3RhbmdsZSBjYW4gYmUgcGFydGlhbGx5IG9yIHRvdGFsbHkgY292ZXJlZCBieSB0aGUgb3RoZXJzLiBUaGUgbGVuZ3RoIG9mIHRoZSBib3VuZGFyeSBvZiB0aGUgdW5pb24gb2YgYWxsIHJlY3RhbmdsZXMgaXMgY2FsbGVkIHRoZSBwZXJpbWV0ZXIuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0byBjYWxjdWxhdGUgdGhlIHBlcmltZXRlci48XC9wPlxyXG5cclxuPHA+QW4gZXhhbXBsZSB3aXRoIDcgcmVjdGFuZ2xlcyBpcyBzaG93biBpbiBGaWd1cmUgMS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9waWN0dXJlLTEuZ2lmXCIgc3R5bGU9XCJoZWlnaHQ6MTU5cHg7IHdpZHRoOjI0OHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAxLiBBIHNldCBvZiA3IHJlY3RhbmdsZXM8XC9wPlxyXG5cclxuPHA+VGhlIGNvcnJlc3BvbmRpbmcgYm91bmRhcnkgaXMgdGhlIHdob2xlIHNldCBvZiBsaW5lIHNlZ21lbnRzIGRyYXduIGluIEZpZ3VyZSAyLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3BpY3R1cmUtMi5naWZcIiBzdHlsZT1cImhlaWdodDoxNTlweDsgd2lkdGg6MjQ4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIDIuIFRoZSBib3VuZGFyeSBvZiB0aGUgc2V0IG9mIHJlY3RhbmdsZXM8XC9wPlxyXG5cclxuPHA+VGhlIHZlcnRpY2VzIG9mIGFsbCByZWN0YW5nbGVzIGhhdmUgaW50ZWdlciBjb29yZGluYXRlcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyB0aGUgbnVtYmVyIG9mIHJlY3RhbmdsZXMgcGFzdGVkIG9uIHRoZSB3YWxsLiBJbiBlYWNoIG9mIHRoZSBzdWJzZXF1ZW50IGxpbmVzLCBvbmUgY2FuIGZpbmQgdGhlIGludGVnZXIgY29vcmRpbmF0ZXMgb2YgdGhlIGxvd2VyIGxlZnQgdmVydGV4IGFuZCB0aGUgdXBwZXIgcmlnaHQgdmVydGV4IG9mIGVhY2ggcmVjdGFuZ2xlLiBUaGUgdmFsdWVzIG9mIHRob3NlIGNvb3JkaW5hdGVzIGFyZSBnaXZlbiBhcyBvcmRlcmVkIHBhaXJzIGNvbnNpc3Rpbmcgb2YgYW4geC1jb29yZGluYXRlIGZvbGxvd2VkIGJ5IGEgeS1jb29yZGluYXRlLjxcL3A+XHJcblxyXG48cD4wICZsdDs9IG51bWJlciBvZiByZWN0YW5nbGVzICZsdDsgNTAwMDxcL3A+XHJcblxyXG48cD5BbGwgY29vcmRpbmF0ZXMgYXJlIGluIHRoZSByYW5nZSBbLTEwMDAwLDEwMDAwXSBhbmQgYW55IGV4aXN0aW5nIHJlY3RhbmdsZSBoYXMgYSBwb3NpdGl2ZSBhcmVhLjxcL3A+XHJcblxyXG48cD5UaGUgbnVtZXJpYyB2YWx1ZSBvZiB0aGUgcmVzdWx0IG1heSBuZWVkIGEgMzItYml0IHNpZ25lZCByZXByZXNlbnRhdGlvbi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IG11c3QgY29udGFpbiBhIHNpbmdsZSBsaW5lIHdpdGggYSBub24tbmVnYXRpdmUgaW50ZWdlciB3aGljaCBjb3JyZXNwb25kcyB0byB0aGUgcGVyaW1ldGVyIGZvciB0aGUgaW5wdXQgcmVjdGFuZ2xlcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > International Olympiad in Informatics > IOI 1998 4번