| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 20 | 14 | 13 | 72.222% |
Пусть задано некоторое множество точек на плоскости. Выпуклая оболочка --- наименьший выпуклый многоугольник, содержащий данные точки.
Необходимо найти число точек с целыми координатами, которые находятся строго внутри выпуклой оболочки заданного множества точек.
Первая строка входного файла содержит целое число $n$ (3ドル \le n \le 100,000円$). Каждая из последующих $n$ строк описывает одну точку и содержит по два целых числа $x_i$ и $y_i$ ($|x_i|, |y_i| \le 10^9$) --- ее координаты. Никакие две точки не совпадают. Среди заданных точек есть три, не лежащие на одной прямой.
В выходной файл выведите ответ на задачу.
5 1 1 1 4 5 4 5 1 2 2
6