Ідеальний маршрут
Limits: 2 sec., 256 MiB
Планування ідеального маршруту для походу — справа нелегка. Для цього в Зеника є детальна карта українських Карпат. На карті позначено \(n\) гір. Координати \(i\)-тої гори \((x_i, y_i)\).
Маршрут можна зобразити як багатокутник на карті. Мандрівники розпочинають шлях у деякій вершині цього багатокутника та йдуть по його сторонах у порядку обходу за годинниковою стрілкою.
Не кожен маршрут є ідеальний. Для Зеника критерії ідеального маршруту такі:
Усі сторони багатокутника паралельні осям координат, він не містить самоперетинів.
Усі гори, що позначені на його карті лежать всередині чи на межі багатокутника.
На маршруті немає двох послідовних поворотів ліворуч.
В Марічки вимоги дещо інші. Єдина її умова — щоб усі повороти на маршруті відбувалися саме на горах, які позначені на карті, а не десь серед лісу. Повороти поза відомими горами, Марічка називає жахливими поворотами.
На жаль, задовольнити вимоги обох мандрівників не завжди можливо. А тому Зеник хоче спланувати маршрут так, щоб він відповідав усім його критеріям та містив якнайменше жахливих поворотів.
Допоможіть Зенику з’ясувати яку найменшу кількість жахливих поворотів може містити маршрут.
Input
У першому рядку задано одне ціло число \(n\) — кількість гір, позначених на карті Зеника.
У наступних \(n\) рядках задано по два цілих числа \(x_i\), \(y_i\) — координати гір. Усі координати гір різні.
Output
У єдиному рядку виведіть одне ціле число — мінімальну кількість жахливих поворотів у маршруті що відповідає критеріям Зеника.
Constraints
\(1 \le n\le 10^{5}\),
\(-10^{9} \le x_i, y_i \le 10^{9}\),
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 3 0 0 1 0 0 1 | 1 |
| Input (stdin) | Output (stdout) |
|---|---|
| 5 0 0 -1 0 1 0 0 -1 0 1 | 3 |
Notes
Маршрут для першого прикладу:
Приклад маршруту з трьома жахливими поворотами для другого прикладу:
Приклад маршруту, який не задовольняє критерії Зеника, адже містить два послідовні повороти ліворуч, якщо рухатися по ньому в порядку обходу за годинниковою стрілкою:
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|