Problems
고대유적지를 탐사하던 경현이는 우연히 고대 문헌 한권을 찾았다. 이 문헌에 따르면 이곳에는 사원이 있었다. 사원은 위에서 보면 정확하게 사각형 모양 이었고, 기둥은 네 모퉁이에 위치하고 있었다.
경현이는 사원의 크기가 아주 크다고 추측을 하고 있다. 기둥들의 위치를 파악하고 4개의 기둥을 이용하여 사원의 크기를 알아보려고 한다.
Input
첫 번째 줄에 기둥의 개수 n(1≤n≤3,000)이 들어온다.
다음 n줄이 들어오는데 각 줄에 기둥의 x, y(0≤x, y≤5,000) 좌표가 공백으로 구분하여 들어온다.
같은 기둥은 2번 이상 들어오지 않는다.
Output
출력은 한 줄에 4개의 기둥으로 만들 수 있는 사원의 최대 면적을 출력한다.
Example
109 44 31 14 22 45 84 05 30 55 2
10
Hint
Source
Japanese Olympiad in Informatics Tokyo Japan 2007 Task 3
You must sign in to write code.