시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1846 622 279 31.000%

문제

2051년, 야심차게 발사한 화성탐사선 성화가 탐사한 곳의 화성 지도를 N개 보냈다.

화성탐사선의 성공에 의기양양해진 BaSA(Baekjoon Space Agency)는 야심찬 계획을 발표했다.

화성 전체 지도를 만들겠습니다!

전체 지도를 만들기 전에, 지금까지 화성탐사선이 보낸 지도를 모두 합쳤다. 이 때, 이 지도의 크기는 몇일까?

탐사선이 보낸 지도는 항상 직사각형 모양이며, 겹칠 수도 있다.

입력

첫째 줄에 화성탐사선 성화가 보낸 지도의 수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 지도의 정보가 주어진다. 지도의 정보는 네 정수 x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ 30,000, 0 ≤ y1 < y2 ≤ 30,000)으로 이루어져 있다. (x1, y1)와 (x2, y2)은 직사각형의 왼쪽 아래 좌표와 오른쪽 위 좌표이다. 모든 지도는 직사각형이고, 변은 항상 x축과 y축에 평행하다.

출력

첫째 줄에 지금까지 탐사선이 보낸 지도를 모두 합쳤을 때, 그 면적을 출력한다. (직사각형을 모두 합쳤을 때 면적)

예제 입력 1

2
10 10 20 20
15 15 25 30

예제 출력 1

225

힌트

W3sicHJvYmxlbV9pZCI6IjMzOTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ2NTRcdWMxMzEgXHVjOWMwXHViM2M0IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHQyMDUxXHViMTQ0LCBcdWM1N2NcdWMyZWNcdWNjMjhcdWFjOGMgXHViYzFjXHVjMGFjXHVkNTVjIFx1ZDY1NFx1YzEzMVx1ZDBkMFx1YzBhY1x1YzEyMCBcdWMxMzFcdWQ2NTRcdWFjMDAgXHVkMGQwXHVjMGFjXHVkNTVjIFx1YWNmM1x1Yzc1OCBcdWQ2NTRcdWMxMzEgXHVjOWMwXHViM2M0XHViOTdjIE5cdWFjMWMgXHViY2Y0XHViMGM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWQ2NTRcdWMxMzFcdWQwZDBcdWMwYWNcdWMxMjBcdWM3NTggXHVjMTMxXHVhY2Y1XHVjNWQwIFx1Yzc1OFx1YWUzMFx1YzU5MVx1YzU5MVx1ZDU3NFx1YzljNCBCYVNBKEJhZWtqb29uIFNwYWNlIEFnZW5jeSlcdWIyOTQgXHVjNTdjXHVjMmVjXHVjYzJjIFx1YWNjNFx1ZDY4ZFx1Yzc0NCBcdWJjMWNcdWQ0NWNcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1ZDY1NFx1YzEzMSBcdWM4MDRcdWNjYjQgXHVjOWMwXHViM2M0XHViOTdjIFx1YjljY1x1YjRlNFx1YWNhMFx1YzJiNVx1YjJjOFx1YjJlNCE8XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjODA0XHVjY2I0IFx1YzljMFx1YjNjNFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWFlMzAgXHVjODA0XHVjNWQwLCBcdWM5YzBcdWFlMDhcdWFlNGNcdWM5YzAgXHVkNjU0XHVjMTMxXHVkMGQwXHVjMGFjXHVjMTIwXHVjNzc0IFx1YmNmNFx1YjBiOCBcdWM5YzBcdWIzYzRcdWI5N2MgXHViYWE4XHViNDUwIFx1ZDU2OVx1Y2NlNFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVjNzc0IFx1YzljMFx1YjNjNFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWIyOTQgXHViYTg3XHVjNzdjXHVhZTRjPzxcL3A+XHJcblxyXG48cD5cclxuXHRcdWQwZDBcdWMwYWNcdWMxMjBcdWM3NzQgXHViY2Y0XHViMGI4IFx1YzljMFx1YjNjNFx1YjI5NCBcdWQ1NmRcdWMwYzEgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1YmFhOFx1YzU5MVx1Yzc3NFx1YmE3MCwgXHVhY2I5XHVjZTYwIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDY1NFx1YzEzMVx1ZDBkMFx1YzBhY1x1YzEyMCBcdWMxMzFcdWQ2NTRcdWFjMDAgXHViY2Y0XHViMGI4IFx1YzljMFx1YjNjNFx1Yzc1OCBcdWMyMTggTigxICZsZTsgTiAmbGU7IDEwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzljMFx1YjNjNFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM5YzBcdWIzYzRcdWM3NTggXHVjODE1XHViY2Y0XHViMjk0IFx1YjEyNCBcdWM4MTVcdWMyMTggeDEsIHkxLCB4MiwgeTIgKDAgJmxlOyB4MSAmbHQ7IHgyICZsZTsgMzAsMDAwLCAwICZsZTsgeTEgJmx0OyB5MiAmbGU7IDMwLDAwMClcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gKHgxLCB5MSlcdWM2NDAgKHgyLCB5MilcdWM3NDAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YzY3Y1x1Y2FiZCBcdWM1NDRcdWI3OTggXHVjODhjXHVkNDVjXHVjNjQwIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM3MDQgXHVjODhjXHVkNDVjXHVjNzc0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjOWMwXHViM2M0XHViMjk0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NFx1YWNlMCwgXHViY2MwXHVjNzQwIFx1ZDU2ZFx1YzBjMSB4XHVjZDk1XHVhY2ZjIHlcdWNkOTVcdWM1ZDAgXHVkM2M5XHVkNTg5XHVkNTU4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjOWMwXHVhZTA4XHVhZTRjXHVjOWMwIFx1ZDBkMFx1YzBhY1x1YzEyMFx1Yzc3NCBcdWJjZjRcdWIwYjggXHVjOWMwXHViM2M0XHViOTdjIFx1YmFhOFx1YjQ1MCBcdWQ1NjlcdWNjZTRcdWM3NDQgXHViNTRjLCBcdWFkZjggXHViYTc0XHVjODAxXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gKFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWJhYThcdWI0NTAgXHVkNTY5XHVjY2U0XHVjNzQ0IFx1YjU0YyBcdWJhNzRcdWM4MDEpPFwvcD5cclxuIiwiaGludCI6IjxwPlxyXG5cdDxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbWFyMC5naWZcIiBzdHlsZT1cIndpZHRoOiAxODhweDsgaGVpZ2h0OiAyNTBweDtcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMzOTIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNYXJzIE1hcHMiLCJkZXNjcmlwdGlvbiI6IjxwPkluIHRoZSB5ZWFyIDIwNTEsIHNldmVyYWwgTWFycyBleHBlZGl0aW9ucyBoYXZlIGV4cGxvcmVkIGRpZmZlcmVudCBhcmVhcyBvZiB0aGUgcmVkIHBsYW5ldCBhbmQgcHJvZHVjZWQgbWFwcyBvZiB0aGVzZSBhcmVhcy4gTm93LCB0aGUgQmFTQSAoQmFsdGljIFNwYWNlIEFnZW5jeSkgaGFzIGFuIGFtYml0aW91cyBwbGFuOiB0aGV5IHdvdWxkIGxpa2UgdG8gcHJvZHVjZSBhIG1hcCBvZiB0aGUgd2hvbGUgcGxhbmV0LiBJbiBvcmRlciB0byBjYWxjdWxhdGUgdGhlIG5lY2Vzc2FyeSBlZmZvcnQsIHRoZXkgbmVlZCB0byBrbm93IHRoZSB0b3RhbCBzaXplIG9mIHRoZSBhcmVhIGZvciB3aGljaCBtYXBzIGFscmVhZHkgZXhpc3QuIEl0IGlzIHlvdXIgdGFzayB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCBjYWxjdWxhdGVzIHRoaXMgYXJlYS48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+cmVhZHMgdGhlIGRlc2NyaXB0aW9uIG9mIG1hcCBzaGFwZXMgZnJvbSB0aGUgaW5wdXQuPFwvbGk+XHJcblx0PGxpPmNvbXB1dGVzIHRoZSB0b3RhbCBhcmVhIGNvdmVyZWQgYnkgdGhlIG1hcHMsPFwvbGk+XHJcblx0PGxpPndyaXRlcyB0aGUgcmVzdWx0IHRvIHRoZSBvdXRwdXQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgYSBzaW5nbGUgaW50ZWdlciBOICgxJmx0Oz1OJmx0Oz0xMCAwMDApLCB0aGUgbnVtYmVyIG9mIGF2YWlsYWJsZSBtYXBzLiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBkZXNjcmliZXMgYSBtYXAuIEVhY2ggb2YgdGhlc2UgbGluZXMgY29udGFpbnMgZm91ciBpbnRlZ2VycyB4PHN1Yj4xPFwvc3ViPiwgeTxzdWI+MTxcL3N1Yj4sIHg8c3ViPjI8XC9zdWI+IGFuZCB5PHN1Yj4yPFwvc3ViPiAoMCZsdDs9eDxzdWI+MTxcL3N1Yj4mbHQ7eDxzdWI+MjxcL3N1Yj4mbHQ7PTMwIDAwMCwgMCZsdDs9eTxzdWI+MTxcL3N1Yj4mbHQ7eTxzdWI+MjxcL3N1Yj4mbHQ7PTMwIDAwMCkuIFRoZSB2YWx1ZXMgKHg8c3ViPjE8XC9zdWI+LHk8c3ViPjE8XC9zdWI+KSBhbmQgKHg8c3ViPjI8XC9zdWI+LHk8c3ViPjI8XC9zdWI+KSBhcmUgdGhlIGNvb3JkaW5hdGVzIG9mLCByZXNwZWN0aXZlbHksIHRoZSBib3R0b20tbGVmdCBhbmQgdGhlIHRvcC1yaWdodCBjb3JuZXIgb2YgdGhlIG1hcHBlZCBhcmVhLiBFYWNoIG1hcCBoYXMgcmVjdGFuZ3VsYXIgc2hhcGUsIGFuZCBpdHMgc2lkZXMgYXJlIHBhcmFsbGVsIHRvIHRoZSB4LSBhbmQgeS1heGlzIG9mIHRoZSBjb29yZGluYXRlIHN5c3RlbS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IHNob3VsZCBjb250YWluIG9uZSBpbnRlZ2VyIEEsIHRoZSB0b3RhbCBleHBsb3JlZCBhcmVhIChpLmUuIHRoZSBhcmVhIG9mIHRoZSB1bmlvbiBvZiBhbGwgcmVjdGFuZ2xlcykuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL21hcjAuZ2lmXCIgc3R5bGU9XCJoZWlnaHQ6MjUwcHg7IHdpZHRoOjE4OHB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2001 5번

Contest > Algorithmic Engagements > PA 2001 6-2번