아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

쉬운 기하

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

요약
주어진 볼록 다각형 안에 들어가고 변이 좌표축에 평행한 직사각형 중 넓이가 가장 큰 값을 구합니다.
난이도

보통10점 중 7점

유형
기하, 투 포인터
정답자
아직 제출이 없습니다

문제

에바는 기하를 공부한다. 지금 배우는 단원은 볼록다각형인데, 에바는 직사각형을 더 좋아한다. 에바의 연습장에는 볼록다각형이 여러 개 그려져 있고, 에바는 각 다각형 안에 들어가는 가장 큰 직사각형의 면적을 알고 싶다.

에바를 도와주자. 볼록다각형이 주어지면 그 안에 들어가는 직사각형의 면적 중 가장 큰 값을 구하면 된다. 직사각형의 각 변은 좌표축과 평행해야 한다.

입력

첫 줄에 다각형의 변의 개수 nn이 주어진다 (3≤n≤100 0003 \le n \le 100\,000). 이어지는 nn개의 줄에는 다각형 꼭짓점의 좌표를 나타내는 정수 xix_i와 yiy_i가 주어진다 (−109≤xi,yi≤109-10^9 \le x_i, y_i \le 10^9). 꼭짓점은 시계 방향으로 주어진다.

주어지는 다각형은 볼록하다.

출력

다각형 안에 들어가고 각 변이 좌표축과 평행한 직사각형 중 면적이 가장 큰 것의 면적을 소수점 아래 여섯째 자리까지 반올림해 한 줄에 출력한다. 소수점 아래 여섯 자리는 항상 모두 채워서 출력한다.

반올림 결과가 갈리는 경계에 놓이는 답은 입력 데이터에 없다.

예제2

  1. 예제 1

    입력
    4
    5 1
    2 4
    3 7
    7 3
    
    예상 출력
    4.000000
    
  2. 예제 2

    입력
    5
    1 1
    1 4
    4 7
    7 4
    7 1
    
    예상 출력
    18.000000