Модуль: Геометрия


Задача

5 /7


Пикап-мастер

Теория Нажмите, чтобы прочитать/скрыть

Точка пересечения

Точка пересечения прямых

a1, b1, c1 - коэффициенты первой прямой,
a2, b2, c2 - коэффициенты второй прямой,
x, y - точка пересечения.

\(x = {-(c1 \cdot b2 - c2 \cdot b1) \over (a1 \cdot b2 - a2 \cdot b1)} \\ y = {-(a1 \cdot c2 - a2 \cdot c1) \over (a1 \cdot b2 - a2 \cdot b1)} \)

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

Теперь научимся делать это с отрезками

Для начала научимся просто проверять их на пересечение.

Отрезки пересекаются, если концы одного находятся по разные стороны от другого и наоборот (это легко проверяется векторным произведением). Единственный случай, когда это не сработает - отрезки лежат на одной прямой. Для него нужно сделать проверку на пересечение т.н. bounding box (ограничивающий прямоугольник отрезка) - проверяем на пересечение проекции отрезков на оси X и Y.

Теперь, когда мы умеем проверять отрезки на пересечение, научимся находить точку (или отрезок) их пересечения:
- если они не пересекаются, то понятно, что такой точки не существует;
- иначе построим прямые, на которых лежат эти отрезки.

Если они параллельны, то отрезки лежат на одной прямой, и нам надо найти отрезок пересечения - от максимальной из левых границ отрезков до минимальной из правых границ (точка меньше другой точки, если она левее, в случае равенства X-координаты - если она ниже).

Если же прямые не параллельны, то найдём точку их пересечения и вернём её.

Задача

Недавно Венцеслав прочитал новую книгу по пикапу, и теперь он хочет опробовать свои знания в парке. Для простоты представим парк в виде набора тропинок, которые являются отрезками на плоскости. Венцеслав уже гулял в этом парке, и знает, какая девушка по какой тропинке гуляет. Проблема в том, что Венцеслав очень ленивый, и гуляет только по одной тропинке. А ещё ему лень узнать, каких девушек он может встретить по пути, и поэтому он попросил Вас, своего лучшего друга, помочь ему в этом непростом деле.
 
Входные данные
В первой строке вводятся координаты концов тропинки (X1, Y1) и (X2, Y2), по которой гуляет Венцеслав (\(-20 <= X1, Y1, X2, Y2 <= 20\)).
Во второй строке вводится целое число N - количество тропинок, по которым гуляют девушки (\(0  <= N <= 5\)).
В последующих N строках вводятся координаты концов тропинок, по которым гуляют девушки (Xi1, Yi1) и (Xi2, Yi2), по i-ой тропинке гуляет i-ая девушка (\(-20 <= X_{i1}, Y_{i1}, X_{i2}, Y_{i2}  <= 20\))
 
Выходные данные
В первой строке выведите число M - количество девушек, пути которых пересекутся с путём Венцеслава (касание путей считается пересечением).
Во второй строке выведите M чисел - номера девушек, с которыми встретится наш герой. Девушки нумеруются с единицы!
 
Примеры
Входные данные Выходные данные
1
0 0 2 2
1
0 2 2 0
1
1

 




time 1000 ms
memory 32 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
PascalABC1
Python4
С++ Mingw-w6417
Комментарий учителя