시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 362 98 45 17.717%

문제

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+XHJcbjxwPjxpbWcgd2lkdGg9XCI1MzNcIiBoZWlnaHQ9XCIxNjFcIiBhbHQ9XCJcIiBzcmM9XCJcL0p1ZGdlT25saW5lXC91cGxvYWRcLzIwMTAwOFwvcmVjdC5QTkdcIiBcLz48XC9wPlxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IFx1YzY3Y1x1Y2FiZFx1Yzc0MCA3XHVhYzFjXHVjNzU4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHViYWE4XHVjMmI1XHVjNzc0XHVhY2UwLCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVhZGY4XHViOWJjXHVjNzQwIFx1YWRmOCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHVkNTY5XHVjOWQxXHVjNzQ0IFx1YWQ2Y1x1ZDU1YyBcdWM2MDhcdWM3NzRcdWIyZTQuIFx1Yzc3NFx1YjdlY1x1ZDU1YyBcdWQ1NjlcdWM5ZDFcdWQ1NjlcdWM3NDQgXHVhZDZjXHVkNTU4XHViYTc0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NzQgXHViMDk4XHVjNjI0XHViMjk0XHViMzcwLCBcdWM3NzQgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YjQ1OFx1YjgwOFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHVjODE1XHViY2Y0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWIxMjQgXHVjODE1XHVjMjE4IHgxLCB5MSwgeDIsIHkyXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0XHViMjk0IFx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWIzMDBcdWFjMDFcdWMxMjBcdWM3M2NcdWI4NWMgXHViOWM4XHVjOGZjIFx1YmNmNFx1YjI5NCBcdWI0NTAgXHVhZjJkXHVjOWMwXHVjODEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCAoeDEsIHkxKSwgKHgyLCB5MilcdWI3N2NcdWIyOTQgXHVjNzU4XHViYmY4XHVjNzc0XHViMmU0LiBcdWM4OGNcdWQ0NWNcdWM3NTggXHViYzk0XHVjNzA0XHViMjk0IC0xMCwwMDBcdWM3NzRcdWMwYzEgMTAsMDAwXHVjNzc0XHVkNTU4XHViODVjIFx1ZDU1Y1x1YjJlNC48XC9wPiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMmY1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIxODUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQaWN0dXJlIiwiZGVzY3JpcHRpb24iOiI8cD5BIG51bWJlciBvZiByZWN0YW5ndWxhciBwb3N0ZXJzLCBwaG90b2dyYXBocyBhbmQgb3RoZXIgcGljdHVyZXMgb2YgdGhlIHNhbWUgc2hhcGUgYXJlIHBhc3RlZCBvbiBhIHdhbGwuIFRoZWlyIHNpZGVzIGFyZSBhbGwgdmVydGljYWwgb3IgaG9yaXpvbnRhbC4gRWFjaCByZWN0YW5nbGUgY2FuIGJlIHBhcnRpYWxseSBvciB0b3RhbGx5IGNvdmVyZWQgYnkgdGhlIG90aGVycy4gVGhlIGxlbmd0aCBvZiB0aGUgYm91bmRhcnkgb2YgdGhlIHVuaW9uIG9mIGFsbCByZWN0YW5nbGVzIGlzIGNhbGxlZCB0aGUgcGVyaW1ldGVyLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdG8gY2FsY3VsYXRlIHRoZSBwZXJpbWV0ZXIuPFwvcD5cclxuXHJcbjxwPkFuIGV4YW1wbGUgd2l0aCA3IHJlY3RhbmdsZXMgaXMgc2hvd24gaW4gRmlndXJlIDEuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcGljdHVyZS0xLmdpZlwiIHN0eWxlPVwiaGVpZ2h0OjE1OXB4OyB3aWR0aDoyNDhweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWd1cmUgMS4gQSBzZXQgb2YgNyByZWN0YW5nbGVzPFwvcD5cclxuXHJcbjxwPlRoZSBjb3JyZXNwb25kaW5nIGJvdW5kYXJ5IGlzIHRoZSB3aG9sZSBzZXQgb2YgbGluZSBzZWdtZW50cyBkcmF3biBpbiBGaWd1cmUgMi48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9waWN0dXJlLTIuZ2lmXCIgc3R5bGU9XCJoZWlnaHQ6MTU5cHg7IHdpZHRoOjI0OHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSAyLiBUaGUgYm91bmRhcnkgb2YgdGhlIHNldCBvZiByZWN0YW5nbGVzPFwvcD5cclxuXHJcbjxwPlRoZSB2ZXJ0aWNlcyBvZiBhbGwgcmVjdGFuZ2xlcyBoYXZlIGludGVnZXIgY29vcmRpbmF0ZXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgdGhlIG51bWJlciBvZiByZWN0YW5nbGVzIHBhc3RlZCBvbiB0aGUgd2FsbC4gSW4gZWFjaCBvZiB0aGUgc3Vic2VxdWVudCBsaW5lcywgb25lIGNhbiBmaW5kIHRoZSBpbnRlZ2VyIGNvb3JkaW5hdGVzIG9mIHRoZSBsb3dlciBsZWZ0IHZlcnRleCBhbmQgdGhlIHVwcGVyIHJpZ2h0IHZlcnRleCBvZiBlYWNoIHJlY3RhbmdsZS4gVGhlIHZhbHVlcyBvZiB0aG9zZSBjb29yZGluYXRlcyBhcmUgZ2l2ZW4gYXMgb3JkZXJlZCBwYWlycyBjb25zaXN0aW5nIG9mIGFuIHgtY29vcmRpbmF0ZSBmb2xsb3dlZCBieSBhIHktY29vcmRpbmF0ZS48XC9wPlxyXG5cclxuPHA+MCAmbHQ7PSBudW1iZXIgb2YgcmVjdGFuZ2xlcyAmbHQ7IDUwMDA8XC9wPlxyXG5cclxuPHA+QWxsIGNvb3JkaW5hdGVzIGFyZSBpbiB0aGUgcmFuZ2UgWy0xMDAwMCwxMDAwMF0gYW5kIGFueSBleGlzdGluZyByZWN0YW5nbGUgaGFzIGEgcG9zaXRpdmUgYXJlYS48XC9wPlxyXG5cclxuPHA+VGhlIG51bWVyaWMgdmFsdWUgb2YgdGhlIHJlc3VsdCBtYXkgbmVlZCBhIDMyLWJpdCBzaWduZWQgcmVwcmVzZW50YXRpb24uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBtdXN0IGNvbnRhaW4gYSBzaW5nbGUgbGluZSB3aXRoIGEgbm9uLW5lZ2F0aXZlIGludGVnZXIgd2hpY2ggY29ycmVzcG9uZHMgdG8gdGhlIHBlcmltZXRlciBmb3IgdGhlIGlucHV0IHJlY3RhbmdsZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d