케이크 자르기

시간 제한2초메모리 제한1024 MB

요약

볼록 다각형이 주어질 때, 두 꼭짓점을 잇는 선으로 나눈 두 조각의 넓이 차이가 가장 작은 경우를 찾습니다.

난이도: 보통10점 중 5점
유형: 기하, 투 포인터, 누적 합
정답자: 아직 제출이 없습니다

문제

기하 기초:

단순 다각형은 자기 자신과 교차하지 않고 구멍이 없는 다각형이다. 서로 교차하지 않는 직선 선분(변)들이 두 개씩 이어져 하나의 닫힌 경로를 이루는 평면 도형이다.
다각형이 볼록하다는 것은, 어떤 변도 포함하지 않는 직선이 다각형과 최대 두 점에서 만난다는 뜻이다.

케이크가 단순 볼록 다각형 모양이다. 직선 한 번으로 케이크를 두 조각으로 자르는데, 이 직선은 다각형의 꼭짓점 두 개를 반드시 지나야 한다. 두 조각의 넓이 차이가 가장 작아지도록 하는 꼭짓점 두 개를 찾아라.

입력

첫 줄에 다각형의 꼭짓점 개수 $n$ ( $4 \le n \le 100$ )이 주어진다. 이어서 $n$ 개의 줄에 각 꼭짓점의 $x$ , $y$ 좌표가 한 줄씩 주어진다. 꼭짓점은 시계 방향 순서로 주어진다. 모든 입력값은 1 이상 $10^3$ 이하의 정수이며, 모든 꼭짓점은 서로 다르다.

출력

두 조각 중 큰 조각과 작은 조각의 넓이 차이를 소수점 첫째 자리까지 출력한다. 예를 들어 0.74는 0.7로, 0.75는 0.8로 출력한다.

예제2

예제 1
입력
```
4
6 4
3 4
4 5
5 5
```
예상 출력
```
1.0
```
예제 2
입력
```
5
10 10
8 15
13 16
18 15
16 10
```
예상 출력
```
15.0
```