직각다각형으로 나뉜 가장 큰 영역

시간 제한1초메모리 제한128 MB

문제

2차원 평면에서 직각다각형은 모든 변이 수평 또는 수직인 다각형이다. 일반 직각다각형은 변끼리 서로 교차할 수 있고, 단순 직각다각형은 변끼리 교차하지 않는 직각다각형이다.

이 문제에서는 다음 조건을 만족하는 일반 직각다각형만 다룬다.

  1. 모든 꼭짓점은 서로 다른 점이다.
  2. 각 꼭짓점에서는 수평 변 하나와 수직 변 하나가 그 꼭짓점에서 만난다.
  3. 변이 교차한다면 항상 수평 변과 수직 변 사이에서만 교차한다. 수평 변끼리 또는 수직 변끼리는 교차하지 않는다.

이러한 일반 직각다각형은 외부를 제외한 평면을 여러 개의 단순 직각다각형 영역으로 나눈다. 주어진 일반 직각다각형이 만드는 단순 직각다각형 영역들 중 면적이 가장 큰 영역의 면적을 구하시오.

입력

첫째 줄에 일반 직각다각형의 꼭짓점 개수 N이 주어진다. (4 <= N <= 1,000)

다음 N개의 줄에는 각 꼭짓점의 좌표를 나타내는 두 정수 x, y가 주어진다. (0 <= x, y <= 10,000)

입력된 순서대로 연속한 두 꼭짓점을 선분으로 잇고, 마지막 꼭짓점과 첫 번째 꼭짓점을 이으면 일반 직각다각형이 만들어진다.

출력

주어진 일반 직각다각형이 나누는 단순 직각다각형 영역 중 면적이 가장 큰 영역의 면적을 첫째 줄에 출력한다.

참고

이 문제의 원래 제목은 "직각다각형의 면적"이다.