아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Столетний дятел

시간 제한2초메모리 제한512 MB

요약
격자에서 다음 칸에 별이 있으면 오른쪽으로만 도는 우주선이 거대한 범위를 벗어날 때까지의 회전 수를 세거나, 영원히 도는지 판정한다.
난이도

보통10점 중 7점

유형
시뮬레이션, 해시맵, 구현
정답자
아직 제출이 없습니다

문제

Карта далёкой-далёкой галактики представляет собой бесконечную плоскость, разбитую на единичные квадраты. Некоторые квадраты заняты звёздами и пролетать через них опасно. Остальные квадраты безопасны. 

Космический корабль <<Столетний дятел>> выходит из червоточины в квадрате (0,0)(0, 0) и изначально движется вправо (то есть в направлении возрастания первой координаты). После тяжёлого сражения у корабля повреждён двигатель, так что корабль может поворачивать только направо на прямой угол. Корабль управляется автопилотом, который в случае, если следующий по текущему курсу квадрат безопасен, перемещает корабль в него, не тратя энергию. В противном случае автопилот остаётся в текущем квадрате и поворачивает, тратя на это одну единицу энергии. 

Требуется определить, сколько единиц энергии потратит корабль, пока одна из его координат не превысит по модулю 101010^{10}, или определить, что этого никогда не произойдёт.

입력

Первая строка входных данных содержит целое число nn --- число звёзд в галактике (0≤n≤10000 \le n \le 1000).

Каждая из последующих nn строк содержит по два целых числа x_ix\_i и y_iy\_i --- координаты очередной звезды (−109≤x_i,y_i≤109-10^9 \le x\_i, y\_i \le 10^9). Гарантируется, что никакие две звезды не находятся в одном квадрате и что в квадрате (0,0)(0, 0) звезды нет.

출력

Выведите одно число --- количество единиц энергии, которое корабль потратит за время путешествия, если оно закончится, или <<oo>>, если этого никогда не произойдёт.

예제2

  1. 예제 1

    입력
    4
    2 0
    -2 -1
    0 3
    1 -3
    
    예상 출력
    2
    
  2. 예제 2

    입력
    8
    1 -1
    1 1
    1 0
    -1 -1
    -1 0
    -1 1
    0 1
    0 -1
    
    예상 출력
    oo