Перетин відрізків#839

Перетин відрізків (Розбір)

Обмежуючий прямокутник геометричної фігури — це найменший прямокутник, сторони якого паралельні осям координат, який повністю містить дану фігуру.

Простіше кажучи, якщо ми хочемо "вписати" фігуру в прямокутник так, щоб усі її точки були всередині, обмежуючий прямокутник буде найменшого розміру.

Розглянемо відрізок з кінцями в точках $(x_{1}, y_{1})$ (x_1, y_1) і $(x_{2}, y_{2})$ (x_2, y_2). Щоб знайти його обмежуючий прямокутник:

Визначимо лівий нижній кут прямокутника:

x_{1}^{'} = min (x_{1}, x_{2}), y_{1}^{'} = min (y_{1}, y_{2})

x_1' = min(x_1, x_2), y_1' = min(y_1, y_2)

Визначимо правий верхній кут прямокутника:

x_{2}^{'} = ma x (x_{1}, x_{2}), y_{2}^{'} = ma x (y_{1}, y_{2})

x_2' = max(x_1, x_2), y_2' = max(y_1, y_2)

Таким чином, обмежуючий прямокутник — це прямокутник з кутами $(x_{1}^{'}, y_{1}^{'})$ (x_1', y_1') і $(x_{2}^{'}, y_{2}^{'})$ (x_2', y_2'), який містить наш відрізок.

Лема. Нехай на прямій задано два відрізки $(x_{1}, x_{2})$ (x_1, x_2) і $(x_{3}, x_{4})$ (x_3, x_4), де $x_{1} < x_{2}$ x_1 < x_2 і $x_{3} < x_{4}$ x_3 < x_4. Відрізки не перетинаються тоді і тільки тоді, коли або перший відрізок розташований лівіше другого, або другий розташований лівіше першого.

Лема. Нехай на площині задано два прямокутника $(x_{1}, y_{1}) - (x_{2}, y_{2})$ (x_1, y_1) - (x_2, y_2) і $(x_{3}, y_{3}) - (x_{4}, y_{4})$ (x_3, y_3) - (x_4, y_4), де $x_{1} < x_{2}, y_{1} < y_{2}$ x_1 < x_2, y_1 < y_2 і $x_{3} < x_{4}, y_{3} < y_{4}$ x_3 < x_4, y_3 < y_4. Прямокутники не перетинаються тоді і тільки тоді, коли або не перетинаються відрізки $(x_{1}, x_{2})$ (x_1, x_2) і $(x_{3}, x_{4})$ (x_3, x_4), або не перетинаються відрізки $(y_{1}, y_{2})$ (y_1, y_2) і $(y_{3}, y_{4})$ (y_3, y_4).

Критерій перетину двох відрізків

Два відрізки $A B$ і $C D$ перетинаються тоді і тільки тоді, коли виконуються три умови:

1. Обмежуючі прямокутники перетинаються.

2. Точки $C$ і $D$ знаходяться по різні сторони від прямої $A B$ або хоча б одна точка $C$ чи $D$ лежить на прямій $A B$ . Це значить, що

[A B \times A C] \cdot [A B \times A D] \leq 0

[AB \times AC] \cdot [AB \times AD] \le 0

3. Точки $A$ і $B$ знаходяться по різні сторони від прямої $C D$ або хоча б одна точка $A$ чи $B$ лежить на прямій $C D$ . Це значить, що

[C D \times C A] \cdot [C D \times C B] \leq 0

[CD \times CA] \cdot [CD \times CB] \le 0

Нижче наведені різні випадки взаємного розташування двох відрізків і відповідні їм значення векторних добутків.

У наступному прикладі кожен з відрізків перетинає пряму, що містить інший відрізок. Однак обмежуючі їх прямокутники не перетинаються.

Приклад

У першому прикладі відрізки перетинаються. У другому прикладі — ні.

Реалізація алгоритму

Оскільки координати кінців відрізків є цілими числами, при обчисленнях ми будемо використовувати лише цілий тип long long. Надалі нам знадобиться функція sgn, яка визначає знак числа $n$ .

int sgn(long long n)
{
  return (n > 0) - (n < 0);
}

Функція RectanglesIntersects приймає як аргументи координати обмежуючих прямокутників для відрізків $A B$ і $C D$ . Вона повертає $1$ , якщо прямокутники $(x_{1}, y_{1}) - (x_{2}, y_{2})$ (x_1, y_1) - (x_2, y_2) і $(x_{3}, y_{3}) - (x_{4}, y_{4})$ (x_3, y_3) - (x_4, y_4) перетинаються, і $0$ в противному випадку.

int RectanglesIntersect(long long x1, long long y1, 
                        long long x2, long long y2,
                        long long x3, long long y3, 
                        long long x4, long long y4)
{
  if (sgn(x3 - x2) * sgn(x4 - x1) > 0) return 0;
  if (sgn(y3 - y2) * sgn(y4 - y1) > 0) return 0;
  return 1;
}

C++

Функція cross обчислює векторний добуток двох векторів $(A_{x}, A_{y})$ (A_x, A_y) і $(B_{x}, B_{y})$ (B_x, B_y).

long long cross(long long Ax, long long Ay, 
                long long Bx, long long By)
{
  return Ax * By - Ay * Bx;
}

Функція intersect перевіряє, чи перетинаються відрізки $A B$ і $C D$ .

int segmentsIntersect(long long x1, long long y1, 
                      long long x2, long long y2,
                      long long x3, long long y3,
                      long long x4, long long y4)
{

Перевіряємо перетин обмежуючих прямокутників. Якщо вони не перетинаються, то повертаємо $0$ .

  if (!RectanglesIntersect(
       min(x1, x2), min(y1, y2), max(x1, x2), max(y1, y2),
       min(x3, x4), min(y3, y4), max(x3, x4), max(y3, y4))
     ) return 0;

Будуємо вектори $A B, A C, A D$ AB, AC, AD.

  long long ABx = x2 - x1, ABy = y2 - y1;
  long long ACx = x3 - x1, ACy = y3 - y1;
  long long ADx = x4 - x1, ADy = y4 - y1;

Будуємо вектори $C D, C A, C B$ CD, CA, CB.

  long long CDx = x4 - x3, CDy = y4 - y3;
  long long CAx = x1 - x3, CAy = y1 - y3;
  long long CBx = x2 - x3, CBy = y2 - y3;

Визначаємо векторні добутки.

  long long ABxAC = cross(ABx, ABy, ACx, ACy); // AB x AC
  long long ABxAD = cross(ABx, ABy, ADx, ADy); // AB x AD
  long long CDxCA = cross(CDx, CDy, CAx, CAy); // CD x CA
  long long CDxCB = cross(CDx, CDy, CBx, CBy); // CD x CB

Перевіряємо пункти $2$ та $3$ критерію перетину відрізків. Якщо вони не виконуються, то повертаємо $0$ . Щоб уникнути переповнення, слід порівнювати з нулем не добуток чисел, а добуток їхніх знаків.

  if (sgn(ABxAC) * sgn(ABxAD) > 0) return 0;
  if (sgn(CDxCA) * sgn(CDxCB) > 0) return 0;
  return 1; // Відрізки перетинаються
}

Основна частина програми. Читаємо вхідні дані.

scanf("%lld %lld %lld %lld",&x1,&y1,&x2,&y2);
scanf("%lld %lld %lld %lld",&x3,&y3,&x4,&y4);

Перевіряємо перетин відрізків.

if (segmentsIntersect(x1, y1, x2, y2, x3, y3, x4, y4))
  puts("Так");
else
  puts("Ні");