Хоёр хэрчим огтлолцох эсэхийг дөрвөн cross product ашиглан шалгадаг арга.

IntermediateХугацаа: O(1)Санах ой: O(1)

Эхлээд жижиг бодлого

A (0, 0)–B (4, 4) ба C (0, 4)–D (4, 0) хэрчим "X" үсэг шиг огтлолцоно.

Cross product-аар: d1 = 16, d2 = −16 тул C ба D нь AB шулууны хоёр өөр талд. d3 = −16, d4 = 16 тул A ба B нь CD шулууны хоёр өөр талд. Хоёулаа хоёр талд тул YES.

Энгийн аргаас санаа руу

Энгийн арга: хоёр шулууны огтлолцох цэгийг бутархайгаар олоод, хоёр хэрчим дээр байгаа эсэхийг шалгана. Зэрэгцээ шулуунд хуваах тэг гарна, бутархайн алдаа гарна.

Гол санаа: огтлолцох цэгийг олох шаардлагагүй. CD хэрчим AB шулууныг гатлах нь C ба D хоёр өөр талд байна гэсэн үг. Мөн эсрэгээр нь. Дөрвөн cross product-ын тэмдэг л хангалттай. Аль нэг d тэг бол цэг шулуун дээр байна. Тэгвэл тэр цэг хэрчмийн хүрээ дотор байгаа эсэхийг шалгана.

Нэр томьёо ба тэмдэглэгээ

cross(O, P, Q)
(P − O) ба (Q − O) сумны cross product. Q цэг OP шулууны аль талд байгааг заана.
d1, d2
C, D цэг AB шулууны аль талд байгаа.
d3, d4
A, B цэг CD шулууны аль талд байгаа.
on(P, Q, R)
R цэг PQ хэрчмийг хүрээлсэн тэгш өнцөгт дотор байгаа эсэх. R шулуун дээр байгаа үед л хэрэглэнэ.
012345678910012345678910ABCDABCD
d1 = 0d2 = 0d3 = 0d4 = 0

AB ба CD хоёр хэрчим огтлолцох уу? Хэрчим бүрийн хувьд нөгөө хэрчмийн хоёр үзүүр аль талд нь байгааг cross product ашиглан шалгана.

Алхам 1 / 7
Хурд
  • AB хэрчим, шалгаж буй цэг
  • CD хэрчим
  • Зүүн тал (эерэг)
  • Баруун тал (сөрөг)
  • Огтлолцол
Слайд 1 / 6

Хоёр зам огтлолцох уу?

Хоёр хэрчим огтлолцох эсэхийг зурж харахад амархан. Компьютерт харин cross product хэрэгтэй: үзүүр бүр нөгөө шулууны аль талд байгааг шалгана.

segment-intersection.cpp
#include <bits/stdc++.h>
using namespace std;
long long ax, ay, bx, by, cx, cy, dx, dy, d1, d2, d3, d4;
bool t;
long long cross(long long ox, long long oy, long long px, long long py, long long qx, long long qy) {
return (px - ox) * (qy - oy) - (py - oy) * (qx - ox);
}
bool on(long long px, long long py, long long qx, long long qy, long long rx, long long ry) {
return min(px, qx) <= rx && rx <= max(px, qx) && min(py, qy) <= ry && ry <= max(py, qy);
}
int main() {
cin >> ax >> ay >> bx >> by >> cx >> cy >> dx >> dy;
d1 = cross(ax, ay, bx, by, cx, cy);
d2 = cross(ax, ay, bx, by, dx, dy);
d3 = cross(cx, cy, dx, dy, ax, ay);
d4 = cross(cx, cy, dx, dy, bx, by);
if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) && ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) {
cout << "YES\n";
return 0;
}
t = (d1 == 0 && on(ax, ay, bx, by, cx, cy)) || (d2 == 0 && on(ax, ay, bx, by, dx, dy)) ||
(d3 == 0 && on(cx, cy, dx, dy, ax, ay)) || (d4 == 0 && on(cx, cy, dx, dy, bx, by));
cout << (t ? "YES" : "NO") << "\n";
}

Юунд хэрэгтэй вэ?

AB ба CD хэрчим огтлолцох (эсвэл хүрэлцэх) эсэхийг бүхэл тоогоор, огтлолцох цэгийг олохгүйгээр шийдэх. Үзүүрээрээ хүрэх, нэг шулуун дээр хэвтэх тохиолдлыг ч зөв шалгана.

Яаж ажилладаг вэ?

1. d1, d2 нь C ба D цэг AB шулууны аль талд байгааг заана (cross product-ын тэмдэг). 2. d3, d4 нь A ба B цэг CD шулууны аль талд байгааг заана. 3. d1, d2 эсрэг тэмдэгтэй бөгөөд d3, d4 ч эсрэг тэмдэгтэй бол хэрчмүүд огтлолцоно: YES. 4. Үгүй бол аль нэг d тэг бөгөөд тэр цэг нөгөө хэрчмийн хүрээ дотор байвал хэрчмүүд хүрэлцэж байна: YES. Бусад үед NO. Оролт: нэг мөрөнд A, B, C, D цэгийн координат (8 тоо).

Яагаад зөв, хэр хурдан бэ?

d1, d2 эсрэг тэмдэгтэй бол CD хэрчим AB шулууныг дайрна. d3, d4 эсрэг тэмдэгтэй бол AB хэрчим CD шулууныг дайрна. Хоёулаа биелбэл огтлолцох цэг хоёр хэрчим дээр зэрэг байна.

Хэрэв аль нэг d тэг бол тэр цэг нөгөө шулуун дээр байна. Шулуун дээрх цэг хэрчим дээр байх нь хэрчмийг хүрээлсэн тэгш өнцөгт дотор байхтай ижил. Бусад үед огтлолцохгүй. Хугацаа O(1), бүгд бүхэл тоогоор.

Түгээмэл алдаа

  • Зөвхөн d1, d2-ыг шалгах. AB богино бол CD шулууныг хүрэхгүй байж болно.
  • d1 * d2 < 0 гэж шалгах. Координат 10⁹ бол d нь 10¹⁸ хүрч, үржвэр нь long long-оос хэтэрнэ. Код тэмдгийг тус тусад нь харьцуулдаг.
  • Хүрэлцэх тохиолдлыг мартах: нэг хэрчмийн үзүүр нөгөө хэрчим дээр байх.
  • Нэг шулуун дээрх хоёр хэрчмийг үргэлж огтлолцоно гэж үзэх. (0, 0)–(2, 2) ба (3, 3)–(5, 5) огтлолцохгүй.

Хязгаарын тохиолдол

  • Үзүүрээрээ хүрэх, (0, 0)–(3, 3) ба (3, 3)–(5, 0): YES.
  • Зэрэгцээ, (0, 0)–(4, 0) ба (0, 1)–(4, 1): бүх d тэг биш, нэг талд, NO.
  • Нэг шулуун дээр давхцах, (0, 0)–(4, 4) ба (1, 1)–(2, 2): YES.
  • Нэг шулуун дээр зайтай, (0, 0)–(2, 2) ба (3, 3)–(5, 5): NO.

Өөрийгөө шалга

  1. (0, 0)–(2, 0) ба (3, −1)–(3, 1) огтлолцох уу?

    Хариу харах

    Үгүй. C ба D нь AB шулууны хоёр талд боловч A ба B нь CD шулууны нэг талд.

  2. d1 = 0 бол юу гэсэн үг вэ?

    Хариу харах

    C цэг AB шулуун дээр байна. Хэрчим дээр эсэхийг on()-оор шалгана.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.A (0, 0)–B (3, 3) ба C (3, 3)–D (5, 0) дээр d1…d4-ийг бодоод хариуг ол.

    Hint харах

    C нь B-тэй давхцаж байна.

    Хариу ба тайлбар

    d1 = 0 (C нь AB дээр), d2 = −15, d3 = −15, d4 = 0. Эсрэг тэмдэгтэй хос алга, гэхдээ C цэг AB хэрчим дээр тул YES.

  2. 2.Огтлолцохдоо "дотроо огтлолцоно" ба "зөвхөн хүрнэ" гэж ялгаж хэвлэ.

    Hint харах

    Эхний if-ийн YES нь дотроо огтлолцох. Хоёр дахь шалгалтын YES нь хүрэлцэх.

    Хариу ба тайлбар

    Эхний нөхцөлд PROPER, t үнэн бол TOUCH, бусад үед NO хэвлэнэ.

  3. 3.n хэрчмээс огтлолцдог хос хэд байгааг тоол (n ≤ 2000).

    Hint харах

    Бүх хосыг шалгахад хэдэн удаа ажиллах вэ?

    Хариу ба тайлбар

    Хос бүрт энэ кодыг ажиллуулна: n(n − 1) / 2 ≈ 2 сая шалгалт, хангалттай хурдан. n = 100 000 бол sweep line хэрэгтэй.

Жишээ

Оролт

1 1 8 7 1 8 9 2

Гаралт

YES