시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB135245818824.672%

문제

좌표 평면에 N (4 ≤ N ≤ 1,500) 개의 점이 주어진다.

서로 다른 점 4개를 선택하면 사각형을 만들 수 있다. 이러한 사각형 중에 직사각형인 것 중 넓이가 가장 큰 것을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 점의 좌표 x y가 주어진다. 점의 좌표는 -10^8보다 크거나 같고, 10^8보다 작거나 같은 정수이다. 점의 좌표는 중복되지 않는다.

출력

가장 큰 직사각형의 넓이를 출력한다.

예제 입력 1

8
-2 3
-2 -1
0 3
0 -1
1 -1
2 1
-3 1
-2 1

예제 출력 1

10

힌트

W3sicHJvYmxlbV9pZCI6IjI0MTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yzg4Y1x1ZDQ1YyBcdWQzYzlcdWJhNzRcdWM1ZDAgTiAoNCAmbGU7IE4gJmxlOyAxLDUwMCkgXHVhYzFjXHVjNzU4IFx1YzgxMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjODEwIDRcdWFjMWNcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTU4XHViYTc0IFx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1YzBhY1x1YWMwMVx1ZDYxNSBcdWM5MTFcdWM1ZDAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc4IFx1YWM4MyBcdWM5MTEgXHViMTEzXHVjNzc0XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVhYzgzXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWMgeCB5XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjODEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCAtMTBeOFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCAxMF44XHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LiBcdWM4MTBcdWM3NTggXHVjODhjXHVkNDVjXHViMjk0IFx1YzkxMVx1YmNmNVx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHViMTEzXHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC85MDBlNWIyYS03MWEwLTRjN2ItOTk3Yi1mZTNjYzY1NjVhY2JcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDIwOHB4OyBoZWlnaHQ6IDE3N3B4O1wiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjQxNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJlY3RhbmdsZSIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSBnaXZlbiBuIHBvaW50cyBvbiB0aGUgY29vcmRpbmF0ZSBwbGFuZS48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHdoaWNoIGNhbGN1bGF0ZXMgdGhlIGxhcmdlc3QgcG9zc2libGUgYXJlYSBvZiBhIHJlY3RhbmdsZSBzdWNoIHRoYXQgZWFjaCBvZiBpdHMgdmVydGljZXMgaXMgb25lIG9mIHRoZSBnaXZlbiBwb2ludHMuIFlvdSBtYXkgYXNzdW1lIHRoYXQgc3VjaCBhIHJlY3RhbmdsZSBleGlzdHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgaXMgcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgXHVmYjAxcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYW4gaW50ZWdlciBuLCB0aGUgbnVtYmVyIG9mIGdpdmVuIHBvaW50cy48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIG4gbGluZXMgY29udGFpbnMgdGhlIGNvb3JkaW5hdGVzIG9mIG9uZSBwb2ludCwgdHdvIGludGVnZXJzIHNlcGFyYXRlZCBieSBhIHNwYWNlLiBUaGUgY29vcmRpbmF0ZXMgd2lsbCBiZSBiZXR3ZWVuICZtaW51czsxMDxzdXA+ODxcL3N1cD4gYW5kIDEwPHN1cD44PFwvc3VwPi48XC9wPlxyXG5cclxuPHA+Tm8gdHdvIHBvaW50cyB3aWxsIGJlIGxvY2F0ZWQgYXQgdGhlIHNhbWUgY29vcmRpbmF0ZXM8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgc2hvdWxkIGJlIHdyaXR0ZW4gdG8gc3RhbmRhcmQgb3V0cHV0LiBUaGUgXHVmYjAxcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIGEgc2luZ2xlIGludGVnZXIsIHRoZSBsYXJnZXN0IHBvc3NpYmxlIGFyZWEgb2YgYSByZWN0YW5nbGUuPFwvcD5cclxuIiwiaGludCI6IjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvOTAwZTViMmEtNzFhMC00YzdiLTk5N2ItZmUzY2M2NTY1YWNiXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAyMDhweDsgaGVpZ2h0OiAxNzdweDtcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+NCAmbGU7IG4gJmxlOyAxLDUwMDxcL2xpPlxyXG48XC91bD5cclxuIn1d

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2009 4번