Выпуклая оболочка

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

요약

정수 좌표 점 n개가 주어질 때, 이들의 볼록 껍질 내부에 있는 정수 좌표 점의 개수를 구한다.

난이도: 어려움10점 중 8점
유형: 기하, 정렬, 정수론
정답자: 아직 제출이 없습니다

문제

Пусть задано некоторое множество точек на плоскости. Выпуклая оболочка --- наименьший выпуклый многоугольник, содержащий данные точки.

Необходимо найти число точек с целыми координатами, которые находятся строго внутри выпуклой оболочки заданного множества точек.

입력

Первая строка входного файла содержит целое число $n$ ( $3 \le n \le 100\\,000$ ). Каждая из последующих $n$ строк описывает одну точку и содержит по два целых числа $x\_i$ и $y\_i$ ( $|x\_i|, |y\_i| \le 10^9$ ) --- ее координаты. Никакие две точки не совпадают. Среди заданных точек есть три, не лежащие на одной прямой.

출력

В выходной файл выведите ответ на задачу.

예제1

예제 1
입력
```
5
1 1
1 4
5 4
5 1
2 2
```
예상 출력
```
6
```