시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB80522413925.045%

문제

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
W3sicHJvYmxlbV9pZCI6IjIxODUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHVkNTY5XHVjOWQxXHVkNTY5IiwiZGVzY3JpcHRpb24iOiI8cD4yXHVjYzI4XHVjNmQwIFx1ZDNjOVx1YmE3NFx1YzBjMVx1YzVkMCBOKDAgJmxlOyBOICZsZTsgNSwwMDApXHVhYzFjXHVjNzU4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1YjRlNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHViNGU0XHVjNzU4IFx1ZDU2OVx1YzlkMVx1ZDU2OVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBoZWlnaHQ9XCIxNjFcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTAwOFwvcmVjdC5QTkdcIiB3aWR0aD1cIjUzM1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IFx1YzY3Y1x1Y2FiZFx1Yzc0MCA3XHVhYzFjXHVjNzU4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViYWE4XHVjMmI1XHVjNzc0XHVhY2UwLCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVhZGY4XHViOWJjXHVjNzQwIFx1YWRmOCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHVkNTY5XHVjOWQxXHVkNTY5XHVjNzQ0IFx1YWQ2Y1x1ZDU1YyBcdWM2MDhcdWM3NzRcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWQ1NjlcdWM5ZDFcdWQ1NjlcdWM3NDQgXHVhZDZjXHVkNTU4XHViYTc0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NzQgXHViMDk4XHVjNjI0XHViMjk0XHViMzcwLCBcdWM3NzQgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YjQ1OFx1YjgwOFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YzgxNVx1YmNmNFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHViMTI0IFx1YzgxNVx1YzIxOCB4MSwgeTEsIHgyLCB5Mlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjI5NCBcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHViMzAwXHVhYzAxXHVjMTIwXHVjNzNjXHViODVjIFx1YjljOFx1YzhmYyBcdWJjZjRcdWIyOTQgXHViNDUwIFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWFjMDAgKHgxLCB5MSksICh4MiwgeTIpXHViNzdjXHViMjk0IFx1Yzc1OFx1YmJmOFx1Yzc3NFx1YjJlNC4gXHVjODhjXHVkNDVjXHVjNzU4IFx1YmM5NFx1YzcwNFx1YjI5NCAtMTAsMDAwXHVjNzc0XHVjMGMxIDEwLDAwMFx1Yzc3NFx1ZDU1OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjJmNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjE4NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBpY3R1cmUiLCJkZXNjcmlwdGlvbiI6IjxwPkEgbnVtYmVyIG9mIHJlY3Rhbmd1bGFyIHBvc3RlcnMsIHBob3RvZ3JhcGhzIGFuZCBvdGhlciBwaWN0dXJlcyBvZiB0aGUgc2FtZSBzaGFwZSBhcmUgcGFzdGVkIG9uIGEgd2FsbC4gVGhlaXIgc2lkZXMgYXJlIGFsbCB2ZXJ0aWNhbCBvciBob3Jpem9udGFsLiBFYWNoIHJlY3RhbmdsZSBjYW4gYmUgcGFydGlhbGx5IG9yIHRvdGFsbHkgY292ZXJlZCBieSB0aGUgb3RoZXJzLiBUaGUgbGVuZ3RoIG9mIHRoZSBib3VuZGFyeSBvZiB0aGUgdW5pb24gb2YgYWxsIHJlY3RhbmdsZXMgaXMgY2FsbGVkIHRoZSBwZXJpbWV0ZXIuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0byBjYWxjdWxhdGUgdGhlIHBlcmltZXRlci48XC9wPlxyXG5cclxuPHA+QW4gZXhhbXBsZSB3aXRoIDcgcmVjdGFuZ2xlcyBpcyBzaG93biBpbiBGaWd1cmUgMS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9waWN0dXJlLTEuZ2lmXCIgc3R5bGU9XCJoZWlnaHQ6MTU5cHg7IHdpZHRoOjI0OHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAxLiBBIHNldCBvZiA3IHJlY3RhbmdsZXM8XC9wPlxyXG5cclxuPHA+VGhlIGNvcnJlc3BvbmRpbmcgYm91bmRhcnkgaXMgdGhlIHdob2xlIHNldCBvZiBsaW5lIHNlZ21lbnRzIGRyYXduIGluIEZpZ3VyZSAyLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3BpY3R1cmUtMi5naWZcIiBzdHlsZT1cImhlaWdodDoxNTlweDsgd2lkdGg6MjQ4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmlndXJlIDIuIFRoZSBib3VuZGFyeSBvZiB0aGUgc2V0IG9mIHJlY3RhbmdsZXM8XC9wPlxyXG5cclxuPHA+VGhlIHZlcnRpY2VzIG9mIGFsbCByZWN0YW5nbGVzIGhhdmUgaW50ZWdlciBjb29yZGluYXRlcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIHRoZSBpbnB1dCBjb250YWlucyB0aGUgbnVtYmVyIG9mIHJlY3RhbmdsZXMgcGFzdGVkIG9uIHRoZSB3YWxsLiBJbiBlYWNoIG9mIHRoZSBzdWJzZXF1ZW50IGxpbmVzLCBvbmUgY2FuIGZpbmQgdGhlIGludGVnZXIgY29vcmRpbmF0ZXMgb2YgdGhlIGxvd2VyIGxlZnQgdmVydGV4IGFuZCB0aGUgdXBwZXIgcmlnaHQgdmVydGV4IG9mIGVhY2ggcmVjdGFuZ2xlLiBUaGUgdmFsdWVzIG9mIHRob3NlIGNvb3JkaW5hdGVzIGFyZSBnaXZlbiBhcyBvcmRlcmVkIHBhaXJzIGNvbnNpc3Rpbmcgb2YgYW4geC1jb29yZGluYXRlIGZvbGxvd2VkIGJ5IGEgeS1jb29yZGluYXRlLjxcL3A+XHJcblxyXG48cD4wICZsdDs9IG51bWJlciBvZiByZWN0YW5nbGVzICZsdDsgNTAwMDxcL3A+XHJcblxyXG48cD5BbGwgY29vcmRpbmF0ZXMgYXJlIGluIHRoZSByYW5nZSBbLTEwMDAwLDEwMDAwXSBhbmQgYW55IGV4aXN0aW5nIHJlY3RhbmdsZSBoYXMgYSBwb3NpdGl2ZSBhcmVhLjxcL3A+XHJcblxyXG48cD5UaGUgbnVtZXJpYyB2YWx1ZSBvZiB0aGUgcmVzdWx0IG1heSBuZWVkIGEgMzItYml0IHNpZ25lZCByZXByZXNlbnRhdGlvbi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IG11c3QgY29udGFpbiBhIHNpbmdsZSBsaW5lIHdpdGggYSBub24tbmVnYXRpdmUgaW50ZWdlciB3aGljaCBjb3JyZXNwb25kcyB0byB0aGUgcGVyaW1ldGVyIGZvciB0aGUgaW5wdXQgcmVjdGFuZ2xlcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > International Olympiad in Informatics > IOI 1998 > Day 2 4번