Гурван цэгийн эргэлтийг ганц үржвэрээр олдог арга: цэг шулууны зүүн талд уу, баруун талд уу, эсвэл дээр нь уу.

Pre-IntermediateХугацаа: O(n)Санах ой: O(n)

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

A (0, 0) цэгээс B (4, 0) цэг рүү баруун тийш алхаж байна. C (2, 3) цэг аль талд байна вэ?

u = B − A = (4, 0), v = C − A = (2, 3). cr = 4 · 3 − 0 · 2 = 12 эерэг тул C цэг зүүн талд: LEFT. Зурж харахад ч C цэг замаас дээш, зүүн гар талд байна.

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

Энгийн арга: шулууны тэгшитгэл y = kx + b гаргаад цэгийг орлуулна. Гэтэл k бутархай гарч болно, босоо шулуунд бүр тодорхойлогдохгүй. Бутархай тооны алдаанаас болж "шулуун дээр" байгаа цэгийг буруу хариулна.

Гол санаа: хоёр сумны cross product ux · vy − uy · vx. Зөвхөн үржүүлэх, хасах үйлдэл тул бүхэл координаттай бол хариу яг бүхэл. Тэмдэг нь л хариу: эерэг бол зүүн, сөрөг бол баруун, тэг бол шулуун дээр.

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

u = B − A
A цэгээс B цэг рүү заасан сум: (bx − ax, by − ay).
v = C − A
A цэгээс шалгах цэг рүү заасан сум.
cr
ux · vy − uy · vx. u ба v сумаар үүсгэсэн параллелограммын тэмдэгтэй талбай.
LEFT, RIGHT, ON
cr эерэг, сөрөг, тэг үеийн хариу.
012345678910012345678910ABCDEF
ux = 0uy = 0vx = 0vy = 0cr = 0

A (1, 2) цэгээс B (9, 6) цэг рүү сум татлаа. Цэг бүр энэ шулууны зүүн талд уу, баруун талд уу, эсвэл яг дээр нь уу? Cross product ганц томьёогоор хэлж өгнө.

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

Зүүн үү, баруун уу?

A цэгээс B цэг рүү алхаж байна гэж бод. Бусад цэг чиний зүүн гар талд уу, баруун гар талд уу? Геометрийн бараг бүх бодлого энэ асуултаас эхэлдэг.

cross-product.cpp
#include <bits/stdc++.h>
using namespace std;
int n;
long long ax, ay, bx, by, x[105], y[105];
long long ux, uy, vx, vy, cr;
int main() {
cin >> ax >> ay >> bx >> by >> n;
for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
ux = bx - ax, uy = by - ay;
for (int i = 0; i < n; i++) {
vx = x[i] - ax, vy = y[i] - ay;
cr = ux * vy - uy * vx;
if (cr > 0) {
cout << "LEFT\n";
} else if (cr < 0) {
cout << "RIGHT\n";
} else {
cout << "ON\n";
}
}
}

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

A цэгээс B цэг рүү татсан шулууны аль талд цэг байгааг бүхэл тоогоор, алдаагүй мэдэх. Хэрчим огтлолцох, гүдгэр хүрээ, олон өнцөгтийн талбай зэрэг геометрийн бараг бүх бодлогын суурь.

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

1. u = B − A нь A цэгээс B цэг рүү заасан сум. 2. Шалгах цэг бүрт v = C − A нь A цэгээс тэр цэг рүү заасан сум. 3. cr = ux · vy − uy · vx. 4. cr > 0 бол цэг зүүн талд (LEFT), cr < 0 бол баруун талд (RIGHT), cr = 0 бол яг шулуун дээр (ON). Оролт: эхний мөрөнд A ба B цэгийн координат, дараа нь n, дараагийн n мөрөнд шалгах цэгүүд.

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

u сумаас v сум руу цагийн зүүний эсрэг эргэвэл cr эерэг, цагийн зүүний дагуу эргэвэл сөрөг. Хоёр сум нэг шулуун дээр хэвтвэл параллелограмм хавтгай болж талбай нь тэг. A цэгээс B цэг рүү харж байхад зүүн тал гэдэг нь яг цагийн зүүний эсрэг эргэлт.

Цэг бүрт хэдхэн үйлдэл: хугацаа O(n). n = 100 000 цэгтэй ч агшин зуур. Координат 10⁹ хүртэл бол үржвэр 10¹⁸ хүртэл хүрэх тул long long заавал.

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

  • Үржвэрийг int-д бодох. Координат 10⁵-аас их бол int хэтэрнэ.
  • Хасах дарааллыг солих: uy · vx − ux · vy гэж бичвэл зүүн, баруун солигдоно.
  • v-г C − B гэж авах. Хоёр сум хоёулаа A цэгээс эхлэх ёстой.
  • double ашиглаад cr == 0 гэж шалгах. Бутархайн алдаанаас болж тэг гарахгүй байж болно.

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

  • Цэг A эсвэл B-тэй давхцах: v = (0, 0) эсвэл v = u тул cr = 0, ON.
  • Босоо шулуун, A (0, 0), B (0, 4): (−1, 2) цэг LEFT, (3, 2) цэг RIGHT. Тэгшитгэлийн аргаас ялгаатай нь ямар ч асуудалгүй.
  • Шулуун дээр боловч AB хэрчмээс гадна байгаа цэг: cr = 0 тул ON. Хэрчим дээр эсэхийг тусад нь шалгана.

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

  1. A (0, 0), B (4, 0) бол (5, −1) цэг аль талд вэ?

    Хариу харах

    RIGHT. cr = 4 · (−1) − 0 · 5 = −4.

  2. A (1, 1), B (3, 5) бол (5, 9) цэг аль талд вэ?

    Хариу харах

    ON. u = (2, 4), v = (4, 8), cr = 2 · 8 − 4 · 4 = 0.

  3. A, B, C гурвалжны талбайг cr-аар яаж олох вэ?

    Хариу харах

    |cr| / 2. cr нь параллелограммын талбай, гурвалжин түүний хагас.

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

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

  1. 1.A (0, 0), B (4, 0) бол (2, 3), (5, −1), (6, 0) цэг бүрт код юу хэвлэх вэ?

    Hint харах

    u = (4, 0) тул cr = 4 · vy. Тэмдгийг нь зөвхөн vy шийднэ.

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

    LEFT, RIGHT, ON.

  2. 2.Кодыг A, B, C гурвалжны талбайг хэвлэдэг болго.

    Hint харах

    Талбай нь |cr| / 2. Сондгой бол .5 төгсгөлтэй.

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

    cr = abs(cr); cout << cr / 2 << (cr % 2 ? ".5" : "") << '\n';. A (0, 0), B (4, 0), C (2, 3) бол 6.

  3. 3.Гурван цэг нэг шулуун дээр байгаа эсэхийг шалга. Цэгүүдийн аль нэг нь давхцаж болно.

    Hint харах

    Давхцсан цэгтэй үед cr ямар байх вэ?

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

    Гурван цэгээс авсан cr тэг бол нэг шулуун дээр. Цэг давхцахад сум нь (0, 0) болж cr тэг гарах тул тэр тохиолдол ч "нэг шулуун дээр" гэж зөв хариулагдана.

Жишээ

Оролт

1 2 9 6 4
3 7
6 2
5 4
9 3

Гаралт

LEFT
RIGHT
ON
RIGHT