Задача C. Космический побег ≡

Условие

Инопланетянин по имени "Скр" живет в плоском мире. Скр снова не доел мамин суп, поэтому теперь он в бегах... Летя на своём корабле он увидел перед собой маленькую планету - круг радиуса r. На планете нет ничего, кроме ярких фонарей. Эти фонари настолько яркие, что освещают на сколько угодно большое расстояние, однако сквозь поверхность планеты они просветить не могут. Всего n фонарей, i-ый фонарь представляет из себя тонкий столб высоты h_i, на верхушке которого располагается светящийся элемент, освещающий все в зоне своей видимости. Укажем точку отчета - произвольную точку на поверхности планеты. И для каждого фонаря известно вещественное число a_i - угол в радианах по часовой стрелки от точки отсчета до основания фонаря (см иллюстрацию).

Скр пытается уйти от погони, поэтому хочет спрятаться в тени, то есть в такой точки планеты, которую не освещает ни один фонарь.

Инопланетянин очень не хочет попасться маме, поэтому просит вас о помощи. Он хочет узнать, есть ли на этой планете место, в котором мог бы спрятаться.

Фонари располагаются перпендикулярно поверхности планеты.

Формат входных данных

В первой строке входных данных располагается целое число n - количество фонарей на планете.

Во второй строке одно вещественное число r - радиус планеты.

В следующих n строках располагаются по два вещественных числа - a_i и h_i - угол в радианах от начальной точки до основания фонаря и высота фонаря.

Формат выходных данных

Выведите в единственной строке YES, если существует место, в котором Скр может спрятаться, и NO в ином случае.

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ r ≤ 100

1 ≤ a_i ≤ 2 * π

0 < h_i < 100

Система оценки и описание подзадач

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

Иллюстрации к примерам

Иллюстрация к примеру 1



Иллюстрация к примеру 2



Иллюстрация к примеру 3

В иллюстрациях начало отсчёта располагается в верхней точке.

Примеры тестов

3
4
1.047197551 1.000000000
3.141592653 2.000000000
5.235987755 0.500000000

YES

3
4
1.047197551 11.000000000
3.141592653 4.000000000
5.235987755 6.000000000

NO

3
4
1.047197551 11.000000000
3.141592653 4.000000000
4.712388980 5.000000000

YES

Разбор

Задачу надо свести к задаче об пересечении отрезков (это известная задача, о ней можно почитать в открытых источниках).

Для каждого фонаря находим две точки - его точки касания, между которыми область, которую этот фонарь освещает. Ту точку, которая по углу ближе к начальной точке, сделать точкой начала отрезка, а вторую точкой его конца.

Сначала надо посчитать сколько отрезков покрывает начальную точку. Далее все точки отсортировать по углу до начальной точки и обойти их по часовой стрелке.

Когда встречаем точку начала отрезка, к счетчику прибавляем единицу, а когда встречаем конец, отнимает единицу. Если в какой-то момент пересекает на счетчике стоит ноль, это означает, что эту существует мы нашли темное место.