시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 2022 683 307 31.846%

문제

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+XHJcblx0XHVjODA0XHVjY2I0IFx1YzljMFx1YjNjNFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWFlMzAgXHVjODA0XHVjNWQwLCBcdWM5YzBcdWFlMDhcdWFlNGNcdWM5YzAgXHVkNjU0XHVjMTMxXHVkMGQwXHVjMGFjXHVjMTIwXHVjNzc0IFx1YmNmNFx1YjBiOCBcdWM5YzBcdWIzYzRcdWI5N2MgXHViYWE4XHViNDUwIFx1ZDU2OVx1Y2NlNFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWM3NzQgXHVjOWMwXHViM2M0XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCBcdWJhODdcdWM3N2NcdWFlNGM/PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1ZDBkMFx1YzBhY1x1YzEyMFx1Yzc3NCBcdWJjZjRcdWIwYjggXHVjOWMwXHViM2M0XHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHViYWE4XHVjNTkxXHVjNzc0XHViYTcwLCBcdWFjYjlcdWNlNjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkNjU0XHVjMTMxXHVkMGQwXHVjMGFjXHVjMTIwIFx1YzEzMVx1ZDY1NFx1YWMwMCBcdWJjZjRcdWIwYjggXHVjOWMwXHViM2M0XHVjNzU4IFx1YzIxOCBOKDEgJmxlOyBOICZsZTsgMTAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVjOWMwXHViM2M0XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzljMFx1YjNjNFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWIyOTQgXHViMTI0IFx1YzgxNVx1YzIxOCB4MSwgeTEsIHgyLCB5MiAoMCAmbGU7IHgxICZsdDsgeDIgJmxlOyAzMCwwMDAsIDAgJmxlOyB5MSAmbHQ7IHkyICZsZTsgMzAsMDAwKVx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiAoeDEsIHkxKVx1YzY0MCAoeDIsIHkyKVx1Yzc0MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHVjNjdjXHVjYWJkIFx1YzU0NFx1Yjc5OCBcdWM4OGNcdWQ0NWNcdWM2NDAgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzcwNCBcdWM4OGNcdWQ0NWNcdWM3NzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWM5YzBcdWIzYzRcdWIyOTQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0XHVhY2UwLCBcdWJjYzBcdWM3NDAgXHVkNTZkXHVjMGMxIHhcdWNkOTVcdWFjZmMgeVx1Y2Q5NVx1YzVkMCBcdWQzYzlcdWQ1ODlcdWQ1NThcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM5YzBcdWFlMDhcdWFlNGNcdWM5YzAgXHVkMGQwXHVjMGFjXHVjMTIwXHVjNzc0IFx1YmNmNFx1YjBiOCBcdWM5YzBcdWIzYzRcdWI5N2MgXHViYWE4XHViNDUwIFx1ZDU2OVx1Y2NlNFx1Yzc0NCBcdWI1NGMsIFx1YWRmOCBcdWJhNzRcdWM4MDFcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiAoXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWQ1NjlcdWNjZTRcdWM3NDQgXHViNTRjIFx1YmE3NFx1YzgwMSk8XC9wPlxyXG4iLCJoaW50IjoiPHA+XHJcblx0PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9tYXIwLmdpZlwiIHN0eWxlPVwid2lkdGg6IDE4OHB4OyBoZWlnaHQ6IDI1MHB4O1wiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzM5MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1hcnMgTWFwcyIsImRlc2NyaXB0aW9uIjoiPHA+SW4gdGhlIHllYXIgMjA1MSwgc2V2ZXJhbCBNYXJzIGV4cGVkaXRpb25zIGhhdmUgZXhwbG9yZWQgZGlmZmVyZW50IGFyZWFzIG9mIHRoZSByZWQgcGxhbmV0IGFuZCBwcm9kdWNlZCBtYXBzIG9mIHRoZXNlIGFyZWFzLiBOb3csIHRoZSBCYVNBIChCYWx0aWMgU3BhY2UgQWdlbmN5KSBoYXMgYW4gYW1iaXRpb3VzIHBsYW46IHRoZXkgd291bGQgbGlrZSB0byBwcm9kdWNlIGEgbWFwIG9mIHRoZSB3aG9sZSBwbGFuZXQuIEluIG9yZGVyIHRvIGNhbGN1bGF0ZSB0aGUgbmVjZXNzYXJ5IGVmZm9ydCwgdGhleSBuZWVkIHRvIGtub3cgdGhlIHRvdGFsIHNpemUgb2YgdGhlIGFyZWEgZm9yIHdoaWNoIG1hcHMgYWxyZWFkeSBleGlzdC4gSXQgaXMgeW91ciB0YXNrIHRvIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IGNhbGN1bGF0ZXMgdGhpcyBhcmVhLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5yZWFkcyB0aGUgZGVzY3JpcHRpb24gb2YgbWFwIHNoYXBlcyBmcm9tIHRoZSBpbnB1dC48XC9saT5cclxuXHQ8bGk+Y29tcHV0ZXMgdGhlIHRvdGFsIGFyZWEgY292ZXJlZCBieSB0aGUgbWFwcyw8XC9saT5cclxuXHQ8bGk+d3JpdGVzIHRoZSByZXN1bHQgdG8gdGhlIG91dHB1dC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyBhIHNpbmdsZSBpbnRlZ2VyIE4gKDEmbHQ7PU4mbHQ7PTEwIDAwMCksIHRoZSBudW1iZXIgb2YgYXZhaWxhYmxlIG1hcHMuIEVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGRlc2NyaWJlcyBhIG1hcC4gRWFjaCBvZiB0aGVzZSBsaW5lcyBjb250YWlucyBmb3VyIGludGVnZXJzIHg8c3ViPjE8XC9zdWI+LCB5PHN1Yj4xPFwvc3ViPiwgeDxzdWI+MjxcL3N1Yj4gYW5kIHk8c3ViPjI8XC9zdWI+ICgwJmx0Oz14PHN1Yj4xPFwvc3ViPiZsdDt4PHN1Yj4yPFwvc3ViPiZsdDs9MzAgMDAwLCAwJmx0Oz15PHN1Yj4xPFwvc3ViPiZsdDt5PHN1Yj4yPFwvc3ViPiZsdDs9MzAgMDAwKS4gVGhlIHZhbHVlcyAoeDxzdWI+MTxcL3N1Yj4seTxzdWI+MTxcL3N1Yj4pIGFuZCAoeDxzdWI+MjxcL3N1Yj4seTxzdWI+MjxcL3N1Yj4pIGFyZSB0aGUgY29vcmRpbmF0ZXMgb2YsIHJlc3BlY3RpdmVseSwgdGhlIGJvdHRvbS1sZWZ0IGFuZCB0aGUgdG9wLXJpZ2h0IGNvcm5lciBvZiB0aGUgbWFwcGVkIGFyZWEuIEVhY2ggbWFwIGhhcyByZWN0YW5ndWxhciBzaGFwZSwgYW5kIGl0cyBzaWRlcyBhcmUgcGFyYWxsZWwgdG8gdGhlIHgtIGFuZCB5LWF4aXMgb2YgdGhlIGNvb3JkaW5hdGUgc3lzdGVtLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gb25lIGludGVnZXIgQSwgdGhlIHRvdGFsIGV4cGxvcmVkIGFyZWEgKGkuZS4gdGhlIGFyZWEgb2YgdGhlIHVuaW9uIG9mIGFsbCByZWN0YW5nbGVzKS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbWFyMC5naWZcIiBzdHlsZT1cImhlaWdodDoyNTBweDsgd2lkdGg6MTg4cHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2001 5번

Contest > Algorithmic Engagements > PA 2001 6-2번