시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 417 78 40 16.260%

문제

좌표 평면에 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

힌트

W3sicHJvYmxlbV9pZCI6IjI0MTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Yzg4Y1x1ZDQ1YyBcdWQzYzlcdWJhNzRcdWM1ZDAgTiAoNCZsdDs9TiZsdDs9MSw1MDApIFx1YWMxY1x1Yzc1OCBcdWM4MTBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+PHA+XHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWM4MTAgNFx1YWMxY1x1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NThcdWJhNzQgXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjMGFjXHVhYzAxXHVkNjE1IFx1YzkxMVx1YzVkMCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NzggXHVhYzgzIFx1YzkxMSBcdWIxMTNcdWM3NzRcdWFjMDAgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFjODNcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWM4MTBcdWM3NTggXHVjODhjXHVkNDVjIHggeVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWIyOTQgLTEwXjhcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMTBeOFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC4gXHVjODEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWM5MTFcdWJjZjVcdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+Iiwib3V0cHV0IjoiPHA+XHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHViMTEzXHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPiIsImhpbnQiOiI8cD48aW1nIHdpZHRoPVwiMjIwXCIgaGVpZ2h0PVwiMTg5XCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDExMDVcL1NjcmVlbiBzaG90IDIwMTEtMDUtMDkgYXQgMTFfMjNfNDIgUE0ucG5nXCIgYWx0PVwiXCIgXC8+PFwvcD4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI0MTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSZWN0YW5nbGUiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgZ2l2ZW4gbiBwb2ludHMgb24gdGhlIGNvb3JkaW5hdGUgcGxhbmUuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB3aGljaCBjYWxjdWxhdGVzIHRoZSBsYXJnZXN0IHBvc3NpYmxlIGFyZWEgb2YgYSByZWN0YW5nbGUgc3VjaCB0aGF0IGVhY2ggb2YgaXRzIHZlcnRpY2VzIGlzIG9uZSBvZiB0aGUgZ2l2ZW4gcG9pbnRzLiBZb3UgbWF5IGFzc3VtZSB0aGF0IHN1Y2ggYSByZWN0YW5nbGUgZXhpc3RzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGlzIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIFx1ZmIwMXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGFuIGludGVnZXIgbiwgdGhlIG51bWJlciBvZiBnaXZlbiBwb2ludHMuPFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBuIGxpbmVzIGNvbnRhaW5zIHRoZSBjb29yZGluYXRlcyBvZiBvbmUgcG9pbnQsIHR3byBpbnRlZ2VycyBzZXBhcmF0ZWQgYnkgYSBzcGFjZS4gVGhlIGNvb3JkaW5hdGVzIHdpbGwgYmUgYmV0d2VlbiAmbWludXM7MTA8c3VwPjg8XC9zdXA+IGFuZCAxMDxzdXA+ODxcL3N1cD4uPFwvcD5cclxuXHJcbjxwPk5vIHR3byBwb2ludHMgd2lsbCBiZSBsb2NhdGVkIGF0IHRoZSBzYW1lIGNvb3JkaW5hdGVzPFwvcD5cclxuXHJcbjxwPjQgJmxlOyBuICZsZTsgMSw1MDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHNob3VsZCBiZSB3cml0dGVuIHRvIHN0YW5kYXJkIG91dHB1dC4gVGhlIFx1ZmIwMXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiBhIHNpbmdsZSBpbnRlZ2VyLCB0aGUgbGFyZ2VzdCBwb3NzaWJsZSBhcmVhIG9mIGEgcmVjdGFuZ2xlLjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMTA1XC9TY3JlZW4gc2hvdCAyMDExLTA1LTA5IGF0IDExXzIzXzQyIFBNLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE4OXB4OyBvcGFjaXR5OjAuOTsgd2lkdGg6MjIwcHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2009 4번