NASA (Норвежская ассоциация астронавтов) разрабатывает новую систему управления космических кораблей. Но в нынешнем состоянии было бы небезопасно, если бы космический корабль оказался в кучке космического мусора. Чтобы система рулевого управления была безопасной, им необходимо ответить на следующее:
Для целевой позиции \(t = (0, 0)\), набора из \(n\) кусков космического мусора \(l\), описанного отрезками \(l_i = ((a_{ix}, a_{iy}), (b_{ix}, b_{iy}))\) и начальной позиции \(s = (s_x, s_y)\), определите существует ли такое направление, что плавание в этом направлении из начальной позиции приведет к целевой позиции.
Когда космический корабль сталкивается с куском космического мусора, то, что происходит дальше, зависит от абсолютной разницы углов между направлением плавания и отрезком космического мусора, \(\theta\):
- Если \(\theta < 45^{\circ}\), то космический корабль скользит по куску космического мусора в направлении, минимизирующем изменение угла, а когда космический корабль оказывается на краю космического мусора, он продолжает двигаться в том же направлении как и до столкновения.
- Если \(\theta \ge 45^{\circ}\), то космический корабль останавливается, потому что трение слишком велико, чтобы скользить по космическому мусору.
Вам дается набор кусочков космического мусора только один раз, целевая позиция всегда \((0, 0)\), но есть \(q\) запросов, каждый с начальной позицией \(s_j = (s_{jx}, s_{jy})\).
Ответьте на приведенный выше вопрос для каждого запроса.
Выходные данные
На каждый запрос \(s_j\) выведите ответ. Если существует такое направление, что плавание от \(s_j\) в этом направлении, возможно, скользя по некоторым частям космического мусора, приводит к \(t\), выведите «YES». В противном случае выведите «NO» (без учета регистра).
Примечание
Синий крест представляет собой целевое местоположение, а другие отрезки синей линии представляют космический мусор.
Зеленые точки обозначают начальные местоположения, где ответ положительный, а красные точки обозначают начальные местоположения, где ответ отрицательный.
Желтые линии — это возможные пути к целевому местоположению для запросов \(3\) и \(14\).
Черная линия — это возможный путь от начального местоположения в запросе \(6\), но он немного не попадает в целевое местоположение.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
0 1 2 4
1 3 -1 6
0 -1 1 -1
14
-2 10
-1 10
0 10
1 10
2 10
3 10
4 10
5 10
6 10
-1 -2
0 -2
1 -2
2 -2
3 -2
|
YES
YES
YES
YES
YES
NO
NO
NO
YES
YES
NO
NO
NO
YES
|