Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Башни - 2

(Время: 1 сек. Память: 16 Мб Сложность: 53%)
Башни - 2

Для того, чтобы защититься от некоторых соседей, король решил построить стену, имеющую форму отрезка. С некоторыми соседями король находится в хороших отношениях, а некоторым готовится объявить войну. Король решил не загораживаться от друзей очень высокой стеной. Однако, стена, отделяющая его от врагов, должна быть достаточно высокой. Было решено, что для наблюдения за прилежащей территорией нужно построить башни. При этом, на участках между башнями высота стен должна изменяться равномерно.

После того, как стена и башни были построены, король заметил, что башни могут быть использованы для наблюдения за состоянием других башен. Однако, некоторые башни оказались очень высокими и загородили другие.

Для каждой башни король попросил вас выяснить, сколько других башен из нее видно.

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

В первой строке входного файла INPUT.TXT находится n (2 ≤ n ≤ 2000) - количество башен стены. В следующих n строках находятся натуральные числа xi и hi (0 ≤ xi ≤ 100000, 1 ≤ hi ≤ 10000) - координата и высота i-ой башни. Все xi различны.

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

Выходной файл OUTPUT.TXT должен содержать n строк. В i-ой строке выведите количество башен, которые видно из башни номер i.

Пример

INPUT.TXTOUTPUT.TXT
111
0 4
3 5
5 3
6 4
7 5
8 8
10 5
12 4
14 3
17 1
19 7
2
5
4
4
4
10
4
4
5
3
5

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483