Оройн координатаас олон өнцөгтийн талбайг шууд олдог Shoelace томьёо.

IntermediateХугацаа: O(n)Санах ой: O(n)
HackerRank дээр бодох

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

Оройнууд нь (0, 0), (4, 0), (4, 4), (0, 4) дөрвөлжингийн талбайг Shoelace томьёогоор олъё.

Ирмэг бүрт x[i] · y[j] − x[j] · y[i]: 0 − 0 = 0, 16 − 0 = 16, 16 − 0 = 16, 0 − 0 = 0. Нийлбэр s = 32. Талбай 32 / 2 = 16, яг 4 · 4.

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

Энгийн арга: олон өнцөгтийг гурвалжнуудад хуваана. Хотгор олон өнцөгтийг зөв хуваах нь төвөгтэй.

Гол санаа: ирмэг бүрийг O (0, 0) цэгтэй холбоод гурвалжин үүсгэнэ. Гурвалжин бүрийн тэмдэгтэй талбайг cross product-аар олно. Олон өнцөгтөөс гадуурх хэсгүүд нэг удаа нэмэгдэж, нэг удаа хасагдаад үгүй болно. Үлдсэн нь яг олон өнцөгтийн талбайг хоёр дахин авсантай тэнцүү.

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

j = (i + 1) % n
Дараагийн орой. Сүүлийн оройн дараа эхний орой руу буцна.
s
x[i] · y[j] − x[j] · y[i] нэмэгдэхүүнүүдийн нийлбэр. Талбайг хоёр дахин авсантай тэнцүү.
Shoelace
Гутлын үдээс шиг солбин үржүүлдэг тул ийм нэртэй томьёо.
чиглэл
Оройг цагийн зүүний эсрэг өгвөл s эерэг, дагуу өгвөл сөрөг.
012345678910012345678910OP0P1P2P3P4
s = 0

5 оройтой олон өнцөгтийн талбайг олъё. Ирмэг бүрийг O (0, 0) цэгтэй холбоод гурвалжин болгоно. Тэдгээрийн талбайг нэмж, хасаад л хариу гарна.

Алхам 1 / 7
Хурд
  • Одоогийн ирмэг
  • Нэмэгдэх гурвалжин
  • Хасагдах гурвалжин
  • Олсон талбай
Слайд 1 / 6

Ямар ч олон өнцөгт

Олон өнцөгтийг гурвалжнуудад хуваах нь төвөгтэй. Shoelace томьёо оройн координатаас талбайг шууд олдог. Ганц loop л хангалттай.

polygon-area.cpp
#include <bits/stdc++.h>
using namespace std;
int n, j;
long long x[105], y[105], s;
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
for (int i = 0; i < n; i++) {
j = (i + 1) % n;
s += x[i] * y[j] - x[j] * y[i];
}
s = abs(s);
cout << s / 2 << (s % 2 ? ".5" : "") << "\n";
}

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

Ямар ч (өөрийгөө огтлохгүй) олон өнцөгтийн талбайг бүхэл тоон үйлдлээр, бутархайн алдаагүй олох. Хариу нь бүхэл тоо, эсвэл бүхэл тоо дээр 0.5 нэмсэн тоо.

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

1. Ирмэг бүр (i, j = (i + 1) % n) нь O (0, 0) цэгтэй гурвалжин үүсгэнэ. 2. x[i] · y[j] − x[j] · y[i] нь энэ гурвалжны тэмдэгтэй талбайг хоёр дахин авсантай тэнцүү. 3. Бүх ирмэгийнхийг нэмэхэд олон өнцөгтөөс гадуурх хэсэг нэг удаа нэмэгдээд, нэг удаа хасагдана. 4. s = |нийлбэр| нь талбайг хоёр дахин авсантай тэнцүү. Хариу = s / 2. Оролт: эхний мөрөнд n, дараагийн n мөрөнд оройнууд хүрээгээр нь тойрох дарааллаар.

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

Ирмэг бүр O цэгтэй гурвалжин үүсгэнэ. Ирмэг O цэгээс харахад цагийн зүүний эсрэг явбал талбай нь нэмэгдэж, дагуу явбал хасагдана. Олон өнцөгт доторх цэг бүр нэмэгдэх гурвалжинд хасагдахаасаа нэгээр илүү удаа ордог. Гадна цэг тэнцүү удаа ордог тул үгүй болно.

Нэг loop тул хугацаа O(n). Бүх үйлдэл бүхэл тоогоор хийгдэх тул хариу нь бүхэл тоо, эсвэл бүхэл тоо дээр 0.5 нэмсэн тоо. Бутархайн алдаа огт гарахгүй.

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

  • abs(s) авахаа мартах. Оройг цагийн зүүний дагуу өгвөл хариу сөрөг гарна.
  • s / 2 гэж бүхэл хуваах. 9 / 2 = 4 болж .5 алдагдана. Код s % 2-ыг шалгаад ".5" нэмдэг.
  • Оройг хүрээгээр нь биш, санамсаргүй дарааллаар өгөх. Shoelace зөвхөн хүрээгээр нь тойрох дараалалд ажиллана.
  • Сүүлийн ирмэгийг (сүүлийн оройноос эхний орой руу) мартах. % n үүнийг л хийдэг.

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

  • Гурвалжин (0, 0), (3, 0), (0, 3): s = 9, хариу 4.5.
  • Хотгор олон өнцөгт (0, 0), (4, 0), (4, 3), (2, 1), (0, 3): хариу 8. Томьёо хотгор үед ч ажиллана.
  • Бүх орой нэг шулуун дээр: s = 0, хариу 0.
  • Өөрийгөө огтолдог олон өнцөгт: хариу утгагүй. Ийм оролт өгөгдөхгүй гэж үздэг.

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

  1. (0, 0), (2, 0), (2, 2), (0, 2) дөрвөлжингийн хувьд s хэд вэ?

    Хариу харах

    8. Талбай нь 4.

  2. Яагаад хариу заавал бүхэл эсвэл .5 төгсгөлтэй вэ?

    Хариу харах

    s бүхэл тоо, хариу нь s / 2.

  3. Дөрвөлжингийн оройг эсрэг дарааллаар өгвөл s хэд болох вэ?

    Хариу харах

    −32. abs авсны дараа хариу 16 хэвээр.

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

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

  1. 1.(1, 1), (9, 2), (4, 8) гурвалжны талбайг ирмэг бүрийн нэмэгдэхүүнээр ол.

    Hint харах

    Гурван нэмэгдэхүүн: 1·2 − 9·1, 9·8 − 4·2, 4·1 − 1·8.

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

    −7 + 64 − 4 = 53. Талбай 26.5.

  2. 2.Оройнууд цагийн зүүний эсрэг өгөгдсөн эсэхийг хэвлэдэг болго.

    Hint харах

    abs авахаас өмнө s-ийн тэмдгийг хар.

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

    abs-ийн өмнө cout << (s > 0 ? "CCW" : "CW") << '\n';. Дөрвөлжинг (0, 4), (4, 4), (4, 0), (0, 0) гэж өгвөл s = −32 тул CW.

  3. 3.Оройнууд нь бүхэл координаттай олон өнцөгтийн дотор хэдэн бүхэл цэг байгааг ол. (Pick-ийн теорем)

    Hint харах

    S = I + B / 2 − 1. B нь хил дээрх бүхэл цэг. Ирмэг дээрх бүхэл цэгийн тоо gcd(|dx|, |dy|).

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

    I = S − B / 2 + 1. Дөрвөлжин (0, 0)–(4, 4): S = 16, B = 16, I = 9. Бүхэл тоогоор бодохын тулд 2I = s − B + 2 хэлбэрээр бич.

Жишээ

Оролт

5
1 1
8 2
9 7
4 9
2 5

Гаралт

42

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.