лооол19

16.02.2020 12:22

Информатика

Есть ответ 👍

Задача B. Мерцающие звёзды Современных звёздных путешественников очень трудно удивить. Однако фирма Amazing Star Travel хочет предложить нечто новое: наблюдения за мерцающими звёздами. Это очень эффектное явление, возникающее в тот момент, когда мощную звезду заслоняет планета. Для этого разработан маршрут между двумя точками A и B. Специалисты фирмы выделили NN наиболее ярких звёзд в видимой части космоса и отметили MM крупных планет. Осталось подсчитать, сколько раз за время путешествия по отрезку AB путешественники насладятся видом мерцающей звезды.

Входные данные.

В первой строке содержится четыре целых числа через пробел XA, YA, XB, YB – координаты точек A и В. Во второй строке содержатся числа NN и MM, разделенные пробелом (0 \leq N,M \leq 1000≤N,M≤100) – количество звёзд и количество планет соответственно. В каждой из следующих N строк содержатся координаты очередной звезды. Далее в каждой из следующих M строк содержатся координаты очередной планеты. Все координаты целые, по модулю не превосходят 1000. Гарантируется, что никакие три точки из всех вышеперечисленных не находятся на одной прямой.

Выходные данные.

В ответе нужно выдать одно число – количество случаев, когда при движении по отрезку из точки A в точку B какая-либо звезда будет заслонена от наблюдателя планетой. Если какие-либо две звезды мерцают одновременно, то это считается как два независимых случая. Все упомянутые объекты считаем материальными точками, для упрощения вычислений все рассматриваем на плоскости. Помимо этого, согласно теории относительности, путешествие с точки зрения внешнего наблюдателя, совершается мгновенно, то есть положение звёзд и планет за время путешествия не изменяется, однако для путешественников оно достаточно длительное, чтобы наладиться захватывающими видами.

Пояснение к примеру

Sample Input:

-4 -2 2 0
3 4
-1 3
2 -1
1 -4
-3 3
-1 0
-2 -2
1 -1

Sample Output:

4