Олимпиадный тренинг

Задача . C. U2


Задача

Темы: геометрия *2400

Недавно Вася узнал, что через любые две точки на плоскости с различными \(x\) координатами можно провести одну и только одну параболу, уравнение которой будет иметь вид \(y = x^2 + bx + c\), где \(b\) и \(c\) — действительные числа. Назовём такую параболу \(U\)-образной.

После этого он нарисовал на плоскости несколько различных точек с целыми координатами и через каждые две из них, имеющие различные координаты \(x\), провёл \(U\)-образную параболу. Рисунок получился откровенно плохой, но Вася не теряет надежды найти число различных получившихся парабол, во внутренней области каждой из которых нет ни одной нарисованной точки. Помогите Васе.

Внутренней областью \(U\)-образной параболы в данной задаче называется часть плоскости, лежащая строго выше параболы, при этом ось \(y\) направлена вверх.

Входные данные

В первой строке находится единственное целое число \(n\) (\(1 \le n \le 100\,000\)) — число точек.

В следующих \(n\) строках находятся описания точек, в \(i\)-й из них находятся 2 целых числа \(x_i\) и \(y_i\) — координаты \(i\)-й точки. Гарантируется, что все точки различные, а так же что координаты по модулю не превосходят \(10^6\).

Выходные данные

В единственной строке выведите единственное число — количество \(U\)-образных парабол, проходящих хотя бы через 2 точки и не содержащих никаких других точек в своей внутренней области (не считая границы).

Примечание

На двух картинках ниже нарисованы все \(U\)-образные параболы, проходящие хотя-бы через 2 отмеченные точки в каждом из двух примеров. Красным отмечены те \(U\)-образные параболы, во внутренней области которых нет ни одной точки.

Первый пример.
Второй пример.

Примеры
Входные данныеВыходные данные
1 3
-1 0
0 2
1 0
2
2 5
1 0
1 -1
0 -1
-1 0
-1 -1
1

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя