Для защиты леса от браконьеров было решено окружить все деревья колючей проволокой. При закупке материалов для забора была допущена ошибка, и теперь у вас есть неограниченный запас проволоки и всего лишь один столб.
Колючую проволоку можно натягивать между двумя деревьями или деревом и столбом только по прямой. Если дерево касается колючей проволоки, его кора повреждается.
Посчитайте, у какого минимального количества деревьев придётся повредить кору при условии, что все деревья должны оказаться в пределах неразрывного замкнутого ограждения из колючей проволоки, а столб можно установить в любую свободную точку плоскости.
В первой строке задано количество деревьев N (3 ≤ N ≤ 105).
Далее следуют N строк с целочисленными координатами деревьев Xi и Yi ( - 106 ≤ Xi, Yi ≤ 106). Гарантируется, что никакие два дерева не расположены в одной точке.
Выведите минимальное количество деревьев, кора которых будет повреждена.
3
0 0
4 2
2 1
3
5
0 1
-5 -2
4 0
2 -2
4 -4
2
Одно из возможных решений для второго примера показано на рисунке (поврежденные деревья помечены крестиками, столб — кружком, колючая проволока — пунктирной линией):
