EduBrick

Сколько слоёв у луковицы

3000 мс · 256 МБ · всё или ничего

Точки на плоскости раскладываются по слоям выпуклой оболочки: первый слой — оболочка всех точек, второй — оболочка оставшихся, и так далее, пока точки не кончатся. Посчитайте количество слоёв.

Формат ввода

В первой строке — число nn (1≤n≤1041 \le n \le 10^4). В следующих nn строках — целые координаты (∣x∣,∣y∣≤104|x|, |y| \le 10^4). Точки могут совпадать.

Формат вывода

Выведите количество слоёв.

Примеры

ввод
5
0 0
4 0
4 4
0 4
2 2
вывод
2
ввод
1
0 0
вывод
1
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.