Бүх цэгийг багтаах хамгийн жижиг гүдгэр олон өнцөгтийг олдог арга (Andrew's monotone chain).

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

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

Цэгүүд: (0, 0), (4, 0), (4, 4), (0, 4), (2, 2). Бүгдийг нь тойрох хамгийн богино хашаа ямар вэ?

Дөрвөлжингийн дөрвөн орой хашааны шон болно. (2, 2) цэг дотор үлдэнэ. Код 4 гээд (0, 0), (4, 0), (4, 4), (0, 4)-ийг хэвлэнэ.

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

Энгийн арга: цэгийн хос бүрийг шалгаад, бусад бүх цэг нэг талд нь байвал тэр хос хүрээний ирмэг гэнэ. Хос n², шалгалт n тул O(n³).

Гол санаа (Andrew's monotone chain): цэгүүдийг зүүнээс баруун тийш эрэмбэлээд доод хэсгийг барина. Хүрээгээр цагийн зүүний эсрэг явахад шон бүр дээр зүүн тийш эргэх ёстой. Шинэ цэг нэмэхэд сүүлийн хоёр цэгтэй баруун тийш эргэж байвал дунд талынх нь хэрэггүй тул хасна. Дараа нь баруунаас зүүн тийш буцаж дээд хэсгийг барина.

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

convex hull
Бүх цэгийг багтаах хамгийн жижиг гүдгэр олон өнцөгт (гүдгэр хүрээ).
h[], k
Хүрээний цэгүүдийг хадгалах Stack ба түүний хэмжээ.
cross(h[k − 2], h[k − 1], p[i])
Сүүлийн хоёр цэгээс p[i] руу эргэх чиглэл. <= 0 бол баруун эсвэл шулуун, тэгвэл хасна.
t
Дээд хэсэг эхлэх үеийн Stack-ийн хэмжээ + 1. Доод хэсгийн цэгүүдийг хасахгүйн тулд.
012345678910012345678910
k = 0
h (хүрээ)
хоосон

9 цэгийг бүгдийг нь багтаах хамгийн жижиг гүдгэр хүрээг олъё. Цэгүүдийг хашаагаар тойруулж байна гэж бод. Хашааны шон бүр дээр зөвхөн зүүн тийш эргэнэ.

Алхам 1 / 30
Хурд
  • Одоогийн цэг
  • Хүрээний хэсэг
  • Хасагдсан
  • Гүдгэр хүрээ
Слайд 1 / 7

Хашаа барина

Талбайд мод ургажээ. Бүх модыг хамгийн богино хашаагаар тойруулъя. Хашаа нь гүдгэр олон өнцөгт болно. Үүнийг гүдгэр хүрээ (convex hull) гэнэ.

convex-hull.cpp
#include <bits/stdc++.h>
using namespace std;
int n, k;
pair<long long, long long> p[105], h[210];
long long cross(pair<long long, long long> o, pair<long long, long long> a, pair<long long, long long> b) {
return (a.first - o.first) * (b.second - o.second) - (a.second - o.second) * (b.first - o.first);
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> p[i].first >> p[i].second;
sort(p, p + n);
n = unique(p, p + n) - p;
for (int i = 0; i < n; i++) {
while (k >= 2 && cross(h[k - 2], h[k - 1], p[i]) <= 0) {
k--;
}
h[k++] = p[i];
}
for (int i = n - 2, t = k + 1; i >= 0; i--) {
while (k >= t && cross(h[k - 2], h[k - 1], p[i]) <= 0) {
k--;
}
h[k++] = p[i];
}
k--;
cout << k << "\n";
for (int i = 0; i < k; i++) cout << h[i].first << " " << h[i].second << "\n";
}

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

Цэгүүдийг тойрох хамгийн богино "хашаа" буюу гүдгэр хүрээг O(n log n) хугацаанд олох. Хамгийн алс хоёр цэг, хүрээний урт, талбай зэрэг олон бодлогын эхний алхам.

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

1. Цэгүүдийг x, дараа нь y утгаар эрэмбэлж, давхардсаныг хасна. 2. Доод хэсэг: зүүнээс баруун тийш явж, цэг бүрийг h Stack-д нэмнэ. Нэмэхийн өмнө сүүлийн хоёр цэгтэй баруун тийш эргэж (эсвэл шулуун) байвал сүүлийнхийг хасна. 3. Дээд хэсэг: баруунаас зүүн тийш буцаж, яг адил дүрмээр үргэлжлүүлнэ. 4. Эхний цэг хоёр удаа орсон тул сүүлийнхийг хасна. h-д хүрээний оройнууд цагийн зүүний эсрэг дарааллаар байна. Оролт: эхний мөрөнд n, дараагийн n мөрөнд цэгүүд. Гаралт: оройн тоо, дараа нь оройнууд.

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

Доод хэсгийг барих явцад h дахь дараалсан гурван цэг бүр зүүн тийш эргэдэг. Хасагдсан цэг өөрийн хоёр хөршөөр үүсгэсэн гурвалжны дотор үлддэг тул хүрээнд орох боломжгүй. Хамгийн зүүн, хамгийн баруун цэг заавал хүрээнд орох тул доод, дээд хэсэг нийлээд бүтэн хүрээ болно.

Цэг бүр Stack-д нэг удаа орж, хамгийн ихдээ нэг удаа гарна. Тиймээс хоёр loop O(n), эрэмбэлэх O(n log n). n = 100 000 бол 2 сая орчим үйлдэл.

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

  • Давхардсан цэгийг хасахгүй байх. unique хийхгүй бол ижил хоёр цэгийн cross тэг гарч, эвдэрнэ.
  • <= 0-ийг < 0 болговол ирмэг дээрх цэгүүд хүрээнд үлдэнэ. Аль нь хэрэгтэйг бодлогоос хар.
  • Дээд хэсгийн loop-д t-гүйгээр k >= 2 гэж бичих. Тэгвэл доод хэсгийн цэгүүдийг хасаад хүрээ эвдэрнэ.
  • Эцэст k-- хийхээ мартах. Эхний цэг хоёр удаа хэвлэгдэнэ.

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

  • Бүх цэг нэг шулуун дээр, (0, 0), (1, 1), (2, 2): хариу 2 цэг, хоёр захынх.
  • Ирмэг дээр цэг байх, (0, 0), (2, 0), (4, 0), (2, 3): (2, 0) хасагдаж 3 оройтой гурвалжин үлдэнэ.
  • Бүх цэг хүрээн дээр, жишээ нь тойрог дээрх цэгүүд: нэг ч цэг хасагдахгүй.

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

  1. (0, 0), (2, 0), (4, 0), (4, 4), (2, 2), (0, 4) цэгийн хүрээ хэдэн оройтой вэ?

    Хариу харах

    4. (2, 0) ирмэг дээр, (2, 2) дотор тул хасагдана.

  2. Хүрээний оройнууд ямар дарааллаар хэвлэгдэх вэ?

    Хариу харах

    Хамгийн зүүн доод цэгээс эхлээд цагийн зүүний эсрэг.

  3. Яагаад loop-ууд O(n) вэ?

    Хариу харах

    Цэг бүр Stack-д нэг удаа орж, нэгээс илүүгүй удаа гарна.

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

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

  1. 1.(0, 0), (2, 0), (4, 0), (2, 3) цэг дээр доод хэсгийг барих алхмуудыг бич.

    Hint харах

    (4, 0) нэмэхэд (0, 0), (2, 0), (4, 0) нэг шулуун дээр. cross ямар гарах вэ?

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

    (0, 0), (2, 0) нэмнэ. (2, 3)-ыг нэмэхэд зүүн тийш эргэх тул үлдэнэ. (4, 0) нэмэхэд (2, 3) дээр баруун тийш эргэх тул хасна, дараа нь (2, 0) шулуун дээр тул хасна. Доод хэсэг: (0, 0), (4, 0).

  2. 2.Ирмэг дээрх цэгүүдийг ч хүрээнд үлдээдэг болго.

    Hint харах

    Зөвхөн хасах нөхцөлийг өөрчил.

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

    <= 0-ийг < 0 болгоно. Гэхдээ бүх цэг нэг шулуун дээр байвал цэгүүд хоёр удаа гарч болохыг анхаар.

  3. 3.Хүрээний периметр ба талбайг ол.

    Hint харах

    Хүрээ бол олон өнцөгт. Polygon Area-ын Shoelace томьёо шууд хэрэглэгдэнэ.

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

    Периметр: хөрш оройнуудын зайны нийлбэр, hypot(dx, dy). Талбай: h дээр Shoelace. Дөрвөлжин (0, 0)–(4, 4) бол периметр 16, талбай 16.

Жишээ

Оролт

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

Гаралт

6
1 2
3 1
7 1
9 4
4 8
2 6

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

Бодлого

Хичээл

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