eolymp
bolt
Try our new interface for solving problems
Məsələlər

Вид на горы

Вид на горы

С пастбища на ферме корова Бесси имеет прекрасный вид на горный хребет на горизонте. Имеются n гор с высотой в диапазоне 1 ... 105. Если смотреть с точки зрения Бесси, то горизонт представляет собой плоскость xy, где каждая гора является треугольником, основание которого опирается на ось x. Обе стороны горы расположены под 45 градусов к основанию, поэтому вершина горы образует прямой угол. Гора i однозначно задается местоположением (xi, yi) ее вершины. Нет двух гор с одинаковым расположением вершин.

Бесси пытается сосчитать все горы, но, поскольку все они примерно одного цвета, то она не может видеть гору, если ее вершина находится на или внутри треугольной формы другой горы.

Определите количество разных вершини, и следовательно гор, которые может видеть Бесси.

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

Первая строка содержит число n (1n105). Каждая из следующих n строк содержит xi (0xi109) и yi (1yi109), описывающих расположение вершины одной горы.

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

Выведите количество гор, которые Бесси может различить.

Пример

В этом примере Бесси может видеть первую и последнюю гору. Вторая гора скрыта за первой.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
3
4 6
7 2
2 5
Çıxış verilənləri #1
2
Mənbə 2019 USACO Январь, Серебро