Задача
Два отрезка на плоскости заданы целочисленными координатами своих концов в декартовой системе координат.
Требуется определить, существует ли у них общая точка.
Входные данные
В первой строке содержатся координаты первого конца первого отрезка, во второй — второго конца первого отрезка, в третьей и четвёртой — координаты концов второго отрезка. Координаты целые и по модулю не превосходят $10000$.
Выходные данные
Вывести слово $Yes$, если общая точка есть, или слово $No$ в противном случае.
Тесты
| № | Входные данные | Выходные данные |
| 1 | 0 0 1 0 1 0 1 1 |
Yes |
| 2 | 0 0 1 0 2 0 3 0 |
No |
| 3 | 7 4 1 1 1 1 3 2 |
Yes |
| 4 | -9725 -8992 9812 9925 -9999 7011 8122 -9248 |
Yes |
| 5 | -9999 -1 10000 1 0 0 0 1 |
No |
Код программы
С ветвлением:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include <iostream> #include <cmath> #define E 1e-5 using namespace std; double length(double x1, double y1, double x2, double y2){ return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); } bool is_include(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, double x, double y){ return ( abs(length(x1, y1, x, y) - length(x1, y1, x2, y2) + length(x, y, x2, y2)) <= E && abs(length(x3, y3, x, y) - length(x3, y3, x4, y4) + length(x, y, x4, y4)) <= E ); } bool is_overlap(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) { return( abs(length(x1, y1, x3, y3) - length(x1, y1, x2, y2) + length(x3, y3, x2, y2)) <= E || abs(length(x1, y1, x4, y4) - length(x1, y1, x2, y2) + length(x4, y4, x2, y2)) <= E || abs(length(x3, y3, x1, y1) - length(x3, y3, x4, y4) + length(x1, y1, x4, y4)) <= E || abs(length(x3, y3, x2, y2) - length(x3, y3, x4, y4) + length(x2, y2, x4, y4)) <= E ); } int main() { long x1, y1, x2, y2, x3, y3, x4, y4; double x, y; cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4; long long ky1, kx1, b1, ky2, kx2, b2; ky1 = y2 - y1; ky2 = y4 - y3; kx1 = x2 - x1; kx2 = x4 - x3; b1 = x1 * y2 - x2 * y1; b2 = x3 * y4 - x4 * y3; if (kx1 * ky2 == kx2 * ky1) { if ( b1 * ky2 != b2 * ky1 && b1 * kx2 != b2 * kx1 ) cout << "No"; else if (is_overlap(x1, y1, x2, y2, x3, y3, x4, y4)) cout << "Yes"; else cout << "No"; } else { y = (double)(b2 * ky1 - b1 * ky2) / (double)(kx1 * ky2 - kx2 * ky1); x = (double)(b1 * kx2 - b2 * kx1) / (double)(ky1 * kx2 - ky2 * kx1); if (is_include(x1, y1, x2, y2, x3, y3, x4, y4, x, y)) cout << "Yes"; else cout << "No"; } return 0; } |
без ветвления:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include <iostream> #include <cmath> #define E 1e-5 using namespace std; double length(double x1, double y1, double x2, double y2){ return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); } bool is_include(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4, double x, double y){ return ( abs(length(x1, y1, x, y) - length(x1, y1, x2, y2) + length(x, y, x2, y2)) <= E && abs(length(x3, y3, x, y) - length(x3, y3, x4, y4) + length(x, y, x4, y4)) <= E ); } bool is_overlap(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) { return( abs(length(x1, y1, x3, y3) - length(x1, y1, x2, y2) + length(x3, y3, x2, y2)) <= E || abs(length(x1, y1, x4, y4) - length(x1, y1, x2, y2) + length(x4, y4, x2, y2)) <= E || abs(length(x3, y3, x1, y1) - length(x3, y3, x4, y4) + length(x1, y1, x4, y4)) <= E || abs(length(x3, y3, x2, y2) - length(x3, y3, x4, y4) + length(x2, y2, x4, y4)) <= E ); } int main() { long x1, y1, x2, y2, x3, y3, x4, y4; double x, y; cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4; long long ky1, kx1, b1, ky2, kx2, b2; ky1 = y2 - y1; ky2 = y4 - y3; kx1 = x2 - x1; kx2 = x4 - x3; b1 = x1 * y2 - x2 * y1; b2 = x3 * y4 - x4 * y3; (kx1 * ky2 == kx2 * ky1) && ( ( b1 * ky2 != b2 * ky1 && b1 * kx2 != b2 * kx1 ) && (cout << "No") || (is_overlap(x1, y1, x2, y2, x3, y3, x4, y4)) && (cout << "Yes") || (cout << "No") ) || ( y = (double)(b2 * ky1 - b1 * ky2) / (double)(kx1 * ky2 - kx2 * ky1), x = (double)(b1 * kx2 - b2 * kx1) / (double)(ky1 * kx2 - ky2 * kx1), (is_include(x1, y1, x2, y2, x3, y3, x4, y4, x, y)) && (cout << "Yes") || (cout << "No") ); return 0; } |
Решение задачи
Чтобы проверить пересекаются ли заданные отрезки построим прямые, которым они принадлежат, затем найдём точку их пересечения и проверим принадлежит ли она каждому из отрезков.
Для построения прямых воспользуемся формулой прямой проходящей через две точки и немного её преобразуем:
$\frac{x — x_1}{x_2 — x_1} = \frac{y — y_1}{y_2 — y_1}$ ~ $(x — x_1) \cdot (y_2 — y_1) = (y — y_1) \cdot (x_2 — x_1)$ ~ $x \cdot (y_2 — y_1) — y_2 \cdot x_1 + y_1 \cdot x_1 = y \cdot (x_2 — x_1) — x_2 \cdot y_1 + x_1 \cdot y_1$ ~ $y \cdot (x_2 — x_1) = x \cdot (y_2 — y_1) + x_2 \cdot y_1 — x_1 \cdot y_2$.
Обозначим за $k_x$ множитель при $x$, за $k_y$ множитель при $y$, а всё остальное за $b$. Тогда имеем уравнение вида:
$y \cdot k_y = x \cdot k_x + b$, таких у нас будет 2:
- $y \cdot k_{y_1} = x \cdot k_{x_1} + b_1$
- $y \cdot k_{y_2} = x \cdot k_{x_2} + b_2$
Теперь рассмотрим несколько случаев:
1. Прямые параллельны, следовательно могут не иметь точки пересечения или совпадать.
Проверим совпадают ли $b_1$ и $b_2$. Так как уравнения не сокращены на НОД, то рассмотрим равенство отношений $b_1$ и $b_2$ на $k_{y_1}$, $k_{x_1}$ и $k_{y_2}$, $k_{x_2}$ соответственно. Если они равны, то прямые совпадают. Иначе не имеют точек пересечения, а следовательно и отрезки тоже не пересекаются.
Когда прямые совпадают, необходимо проверить, что отрезки на этой прямой имеют хоть какую-то общую точку. Каждый из концов каждого отрезка проверим на вхождение в другой. Если такое вхождение есть, то отрезки пересекаются, иначе нет.
2. Прямые не параллельны, а следовательно имеют точку пересечения.
Тогда, решив систему двух линейных уравнений в общем виде получим что:
- $x = \frac{b_1 \cdot k_{x_2} — b_2 \cdot k_{x_1}}{k_{y_1} \cdot k_{x_2} — k_{x_1} \cdot k_{y_2}}$
- $y = \frac{b_2 \cdot k_{y_1} — b_1 \cdot k_{y_2}}{k_{x_1} \cdot k_{y_2} — k_{y_1} \cdot k_{x_2}}$
Осталось проверить находится ли точка с координатами $(x, y)$ в каждом из отрезков. Для этого просуммируем расстояния от этой точки до границ каждого отрезка и сравним с длинами отрезков. Если суммы соответственно совпали с длинами, то отрезки пересекаются, иначе — нет.