|
Башни - 2
(Время: 1 сек. Память: 16 Мб Сложность: 53%)
Для того, чтобы защититься от некоторых соседей, король решил построить стену, имеющую форму отрезка. С некоторыми соседями король находится в хороших отношениях, а некоторым готовится объявить войну. Король решил не загораживаться от друзей очень высокой стеной. Однако, стена, отделяющая его от врагов, должна быть достаточно высокой. Было решено, что для наблюдения за прилежащей территорией нужно построить башни. При этом, на участках между башнями высота стен должна изменяться равномерно.
После того, как стена и башни были построены, король заметил, что башни могут быть использованы для наблюдения за состоянием других башен. Однако, некоторые башни оказались очень высокими и загородили другие.
Для каждой башни король попросил вас выяснить, сколько других башен из нее видно.
Входные данные
В первой строке входного файла INPUT.TXT находится n (2 ≤ n ≤ 2000) - количество башен стены. В следующих n строках находятся натуральные числа xi и hi (0 ≤ xi ≤ 100000, 1 ≤ hi ≤ 10000) - координата и высота i-ой башни. Все xi различны.
Выходные данные
Выходной файл OUTPUT.TXT должен содержать n строк. В i-ой строке выведите количество башен, которые видно из башни номер i.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 11
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 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
