0288. Прикладная флористика

Input file name: flowers.in
Output file name: flowers.out
Time limit: 3 s
Memory limit: 256 megabytes

Серёжа подарил Ане на день рождения n цветов различных видов. В энциклопедии Аня прочитала, что i–ый цветок вырастает со скоростью vi сантиметров в день и его изначальный рост равен hi сантиметров. Ане сразу же посадила все n цветов на грядку и теперь бегает каждый день и проверяет – не <<обогнал>> ли какой-нибудь цветок другого в росте. Серёже не нравится, что Аня всё своё свободное время проводит с цветами. Теперь его интересует, когда наступит день, после которого ни один другой цветок не сможет обогнать никакой другой цветок. Серёжа просит вас помочь ему определить этот день.

Рассмотрим процесс роста цветов на примере:
Пусть Ане подарили три цветка. Рост первого цветка 5 сантиметров, второго – 7 сантиметров, третьего – 1 сантиметр. Скорость роста первого цветка 2 сантиметра в день, второго – 1 сантиметр в день, третьего – 3 сантиметра в день.

Изначально (в нулевой день) у цветов следующие высоты: 5  7  1.

В первый день: 7  8  4.

Во второй день: 9  9  7.

В третий день: 11  10  10 (первый цветок обогнал второй).

В четвертый день: 13  11  13 (третий цветок обогнал второй).

В пятый день: 15  12  16 (третий цветок обогнал первый).

Начиная с пятого дня никакие два цветка уже не обгонят друг друга, поэтому ответом является число 5.

Формат входного файла

В первой строке входного файла дано целое число n – количество различных видов цветов (1 ≤ n ≤ 105). В следующих n строках даны по два целых числа hi и vi – изначальный рост i–ого цветка и его скорость роста соответственно (0 ≤ hi, vi ≤ 109).

Формат выходного файла

В выходной файл выведите единственное число – номер искомого дня.

Пример:

flowers.inflowers.out
3 5 2 7 1 1 3 5
1 0 0 0
2 5 1 6 1 0
Первый пример разобран в условии. Во втором примере есть всего один цветок, ему некого обгонять, поэтому ответ 0. В третьем примере цветки уже не могут обогнать друг друга, поэтому ответ 0.


Source: Первенство ПетрГУ. Сентябрь 2012.

Discuss       Submit a solution



Printable version