시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 64 MB81120.000%

문제

직사각형 모양의 과수원들이 옹기종기 모여 있는 넓은 벌판이 있다. 서로 다른 과수원들은 겹쳐 있지는 않지만, 변을 공유할 있을 수는 있다. 각각의 과수원에는 한 종류의 과일만이 심어져 있다. 물론 서로 다른 과수원에 같은 종류의 과일이 심어져 있을 수도 있다. 아래는 비행기를 타고 상공에서 바라본 두 개의 벌판을 그림으로 도식화한 것이다. 같은 색으로 그려진 직사각형은 같은 종류의 과일이 심어져 있는 과수원이 된다.

같은 색으로 칠해진 직사각형 중에서 가장 큰 것의 넓이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 과수원의 개수 N(1 ≤ N ≤ 2,500)이 주어진다. 이어서 다음 N개 줄에는 다섯 개의 정수 X1, Y1, X2, Y2, C가 빈 칸을 사이에 두고 주어진다. (X1 < X2, Y1 < Y2) 이는 과수원이 (X1, Y1), (X2, Y2)를 두 꼭짓점으로 하는 직사각형이라는 뜻이다. 의미한다. 좌표는 0 이상 1,000,000,000 이하의 정수이다. C는 이 과수원에 심어져 있는 과일의 종류를 나타내는 번호이다. (1 ≤ C ≤ 100)

출력

같은 색으로 칠해진 직사각형 중에서 가장 큰 것의 넓이를 출력한다.

예제 입력 1

5
1 1 3 3 1
3 1 5 3 1
1 4 3 6 1
3 4 5 6 1
0 3 6 4 2

예제 출력 1

8

예제 입력 2

5
5 5 6 6 22
3 4 6 5 22
6 3 7 6 22
5 6 8 7 22
4 5 5 8 22

예제 출력 2

9

예제 입력 3

7
0 0 4 3 1
6 2 9 7 2
6 7 10 9 3
4 0 6 3 1
0 6 6 9 3
0 3 6 6 2
7 0 8 2 2

예제 출력 3

27
W3sicHJvYmxlbV9pZCI6IjE4MzEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZmNcdWMyMThcdWM2ZDAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWJhYThcdWM1OTFcdWM3NTggXHVhY2ZjXHVjMjE4XHVjNmQwXHViNGU0XHVjNzc0IFx1YzYzOVx1YWUzMFx1Yzg4NVx1YWUzMCBcdWJhYThcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YjExM1x1Yzc0MCBcdWJjOGNcdWQzMTBcdWM3NzQgXHVjNzg4XHViMmU0LiBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YWNmY1x1YzIxOFx1YzZkMFx1YjRlNFx1Yzc0MCBcdWFjYjlcdWNjZDAgXHVjNzg4XHVjOWMwXHViMjk0IFx1YzU0YVx1YzljMFx1YjljYywgXHViY2MwXHVjNzQ0IFx1YWNmNVx1YzcyMFx1ZDU2MCBcdWM3ODhcdWM3NDQgXHVjMjE4XHViMjk0IFx1Yzc4OFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YWNmY1x1YzIxOFx1YzZkMFx1YzVkMFx1YjI5NCBcdWQ1NWMgXHVjODg1XHViOTU4XHVjNzU4IFx1YWNmY1x1Yzc3Y1x1YjljY1x1Yzc3NCBcdWMyZWNcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWJiM2NcdWI4NjAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWFjZmNcdWMyMThcdWM2ZDBcdWM1ZDAgXHVhYzE5XHVjNzQwIFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWFjZmNcdWM3N2NcdWM3NzQgXHVjMmVjXHVjNWI0XHVjODM4IFx1Yzc4OFx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LiBcdWM1NDRcdWI3OThcdWIyOTQgXHViZTQ0XHVkNTg5XHVhZTMwXHViOTdjIFx1ZDBjMFx1YWNlMCBcdWMwYzFcdWFjZjVcdWM1ZDBcdWMxMWMgXHViYzE0XHViNzdjXHViY2Y4IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHViYzhjXHVkMzEwXHVjNzQ0IFx1YWRmOFx1YjliY1x1YzczY1x1Yjg1YyBcdWIzYzRcdWMyZGRcdWQ2NTRcdWQ1NWMgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWFjMTlcdWM3NDAgXHVjMGM5XHVjNzNjXHViODVjIFx1YWRmOFx1YjgyNFx1YzljNCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDAgXHVhYzE5XHVjNzQwIFx1Yzg4NVx1Yjk1OFx1Yzc1OCBcdWFjZmNcdWM3N2NcdWM3NzQgXHVjMmVjXHVjNWI0XHVjODM4IFx1Yzc4OFx1YjI5NCBcdWFjZmNcdWMyMThcdWM2ZDBcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzZjMDc1ZGExLTk5NWUtNGVlNC05N2Q4LWY3Mjg5MWZmMTEyMFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNTI0cHg7IGhlaWdodDogMTI5cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YWMxOVx1Yzc0MCBcdWMwYzlcdWM3M2NcdWI4NWMgXHVjZTYwXHVkNTc0XHVjOWM0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFjODNcdWM3NTggXHViMTEzXHVjNzc0XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjZmNcdWMyMThcdWM2ZDBcdWM3NTggXHVhYzFjXHVjMjE4IE4oMSAmbGU7IE4gJmxlOyAyLDUwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWM1YjRcdWMxMWMgXHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjJlNFx1YzEyZiBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IFgxLCBZMSwgWDIsIFkyLCBDXHVhYzAwIFx1YmU0OCBcdWNlNzhcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChYMSAmbHQ7IFgyLCBZMSAmbHQ7IFkyKSBcdWM3NzRcdWIyOTQgXHVhY2ZjXHVjMjE4XHVjNmQwXHVjNzc0IChYMSwgWTEpLCAoWDIsIFkyKVx1Yjk3YyBcdWI0NTAgXHVhZjJkXHVjOWQzXHVjODEwXHVjNzNjXHViODVjIFx1ZDU1OFx1YjI5NCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NzRcdWI3N2NcdWIyOTQgXHViNzNiXHVjNzc0XHViMmU0LiBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuIFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCAwIFx1Yzc3NFx1YzBjMSAxLDAwMCwwMDAsMDAwIFx1Yzc3NFx1ZDU1OFx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuIENcdWIyOTQgXHVjNzc0IFx1YWNmY1x1YzIxOFx1YzZkMFx1YzVkMCBcdWMyZWNcdWM1YjRcdWM4MzggXHVjNzg4XHViMjk0IFx1YWNmY1x1Yzc3Y1x1Yzc1OCBcdWM4ODVcdWI5NThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YmM4OFx1ZDYzOFx1Yzc3NFx1YjJlNC4gKDEgJmxlOyBDICZsZTsgMTAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMxOVx1Yzc0MCBcdWMwYzlcdWM3M2NcdWI4NWMgXHVjZTYwXHVkNTc0XHVjOWM0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFjODNcdWM3NTggXHViMTEzXHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxODMxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoicG9samEiLCJkZXNjcmlwdGlvbiI6IjxwPk1pY2tleSBpcyBpbiB0aGUgYWlycGxhbmUgYWJvdmUgZ3JvdW5kLiBPbiB0aGUgZ3JvdW5kLCBoZSBzZWVzIGZpZWxkcyBvZiByZWN0YW5ndWxhciBzaGFwZXMgYW5kIGRpZmZlcmVudCBjb2xvcnMsIGRlcGVuZGluZyBvbiBwbGFudGVkIHZlZ2V0YXRpb24uJm5ic3A7PFwvcD5cclxuXHJcbjxwPk1pY2tleSB3YW50cyB0byBrbm93IHdoYXQgaXMgdGhlIGFyZWEgb2YgdGhlIGxhcmdlc3Qgb25lLWNvbG9yZWQgcmVjdGFuZ2xlIG9uIHRoZSBncm91bmQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk9uIHRoZSBwaWN0dXJlIHlvdSBjYW4gc2VlIGV4YW1wbGVzIGZyb20gdGhlIGJvdHRvbSBvZiB0aGUgcGFnZSAoc29sdXRpb24gZm9yIGVhY2ggZXhhbXBsZSBpcyBtYXJrZWQpOiZuYnNwOzxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcLzZjMDc1ZGExLTk5NWUtNGVlNC05N2Q4LWY3Mjg5MWZmMTEyMFwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNTI0cHg7IGhlaWdodDogMTI5cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgY2FsY3VsYXRlIHRoZSBhcmVhIG9mIHRoZSBsYXJnZXN0IG9uZS1jb2xvcmVkIHJlY3RhbmdsZSBvbiB0aGUgZ3JvdW5kLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ud28gZGlmZmVyZW50IGZpZWxkcyB3aWxsIG5vdCBvdmVybGFwLCBob3dldmVyIHRoZXkgbWF5IHRvdWNoIGluIGNvcm5lcnMgb3IgYWxvbmcgc2lkZXMuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5GaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGFuIGludGVnZXIgTiwgMSAmbGU7IE4gJmxlOyAyNTAwLCB0aGUgbnVtYmVyIG9mIGZpZWxkcyBvbiB0aGUgZ3JvdW5kLiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyBmaXZlIGludGVnZXJzIFgxLCBZMSwgWDIsIFkyIChYMSZsdDtYMiwgWTEmbHQ7WTIpIGFuZCBDLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGVzZSBudW1iZXJzIHJlcHJlc2VudHMgb25lIGZpZWxkICh3aXRoIHNpZGVzIHBhcmFsbGVsIHRvIGNvb3JkaW5hdGUgYXhlcykgd2l0aCBjb29yZGluYXRlcyBvZiBkaWFnb25hbCBjb3JuZXJzIChYMSxZMSkgYW5kIChYMixZMikgYW5kIHdpdGggY29sb3IgQywgMSAmbGU7IEMgJmxlOyAxMDAuIEFsbCB0aGUgY29vcmRpbmF0ZXMgd2lsbCBiZSBpbnRlZ2VycyBiZXR3ZWVuIDAgYW5kIDEsMDAwLDAwMCwwMDAgKGluY2x1c2l2ZSkuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gdGhlIGFyZWEgZnJvbSB0aGUgcHJvYmxlbSBzdGF0ZW1lbnQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vdGU6IHNvbHV0aW9uIHdpbGwgYWx3YXlzIGZpdCBpbnRvIHRoZSBzaWduZWQgNjQtYml0IGludGVnZXIgZGF0YSB0eXBlIChpbnQ2NCBpbiBQYXNjYWwsIGxvbmcgbG9uZyBpbiBDXC9DKyspLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2005 > Final Exam #2 2번

  • 문제를 번역한 사람: author5