시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 512 MB | 2 | 2 | 2 | 100.000% |
Карта далёкой-далёкой галактики представляет собой бесконечную плоскость, разбитую на единичные квадраты. Некоторые квадраты заняты звёздами и пролетать через них опасно. Остальные квадраты безопасны.
Космический корабль <<Столетний дятел>> выходит из червоточины в квадрате $(0, 0)$ и изначально движется вправо (то есть в направлении возрастания первой координаты). После тяжёлого сражения у корабля повреждён двигатель, так что корабль может поворачивать только направо на прямой угол. Корабль управляется автопилотом, который в случае, если следующий по текущему курсу квадрат безопасен, перемещает корабль в него, не тратя энергию. В противном случае автопилот остаётся в текущем квадрате и поворачивает, тратя на это одну единицу энергии.
Требуется определить, сколько единиц энергии потратит корабль, пока одна из его координат не превысит по модулю $10^{10}$, или определить, что этого никогда не произойдёт.
Первая строка входных данных содержит целое число $n$ --- число звёзд в галактике ($0 \le n \le 1000$).
Каждая из последующих $n$ строк содержит по два целых числа $x_i$ и $y_i$ --- координаты очередной звезды ($-10^9 \le x_i, y_i \le 10^9$). Гарантируется, что никакие две звезды не находятся в одном квадрате и что в квадрате $(0, 0)$ звезды нет.
Выведите одно число --- количество единиц энергии, которое корабль потратит за время путешествия, если оно закончится, или <<oo
>>, если этого никогда не произойдёт.
4 2 0 -2 -1 0 3 1 -3
2
8 1 -1 1 1 1 0 -1 -1 -1 0 -1 1 0 1 0 -1
oo