Огтлолцох хэрчмийн хосыг хайх¶
Хавтгай дээр $n$ хэрчим өгөгдсөн. Тэдгээрийн дор хаяж хоёр нь хоорондоо огтлолцож байгаа эсэхийг шалгах шаардлагатай. Хэрэв хариулт нь тийм бол огтлолцох хэрчмүүдийн энэ хосыг хэвлэ; хэд хэдэн хариултын дундаас алийг нь ч сонгоход хангалттай.
Гэнэн шийдийн алгоритм бол $O(n^2)$-д хэрчмүүдийн бүх хосыг тойрч, хос бүрийн хувьд тэдгээр огтлолцож байгаа эсэхийг шалгах явдал юм. Энэ өгүүлэлд шүүрдэх шулууны алгоритм дээр суурилсан $O(n \log n)$ ажиллах хугацаатай алгоритмыг тайлбарлана.
Алгоритм¶
$x = -\infty$ босоо шулууныг төсөөлөн зураад энэ шулууныг баруун тийш хөдөлгөж эхэлье. Хөдлөх явцдаа энэ шулуун хэрчмүүдтэй тааралдах ба хэрчим бидний шулуунтай огтлолцох бүрд яг нэг цэгт огтлолцоно (бид босоо хэрчим байхгүй гэж үзнэ).
Ингэснээр хэрчим бүрийн хувьд ямар нэг цаг мөчид түүний цэг шүүрдэх шулуун дээр гарч ирэх ба дараа нь шулууны хөдөлгөөнтэй хамт энэ цэг хөдөлж, эцэст нь ямар нэг мөчид хэрчим шулуунаас алга болно.
Бид босоо тэнхлэгийн дагуух хэрчмүүдийн харьцангуй эрэмбийг сонирхож байна. Тодруулбал бид өгөгдсөн цаг мөчид шүүрдэх шулууныг огтолж буй хэрчмүүдийн жагсаалтыг хадгалах ба хэрчмүүдийг шүүрдэх шулуун дээрх $y$ координатаар нь эрэмбэлнэ.
Энэ эрэмбэ сонирхолтой, учир нь огтлолцох хэрчмүүд дор хаяж нэг мөчид ижил $y$ координаттай байх болно:
Гол мэдэгдлүүдийг томьёолъё:
- Огтлолцох хосыг олохын тулд шүүрдэх шулууны тогтмол байрлал бүрд зөвхөн зэргэлдээ хэрчмүүдийг авч үзэхэд хангалттай.
- Шүүрдэх шулууныг боломжит бүх бодит байрлалд $(-\infty \ldots +\infty)$ биш, харин зөвхөн шинэ хэрчим гарч ирэх эсвэл хуучин нь алга болох байрлалуудад авч үзэхэд хангалттай. Өөрөөр хэлбэл өөрийгөө зөвхөн хэрчмүүдийн үзүүрийн цэгүүдийн абсциссатай тэнцүү байрлалуудаар хязгаарлахад хангалттай.
- Шинэ хэрчим гарч ирэхэд түүнийг өмнөх шүүрдэх шулууны хувьд гарсан жагсаалтын шаардлагатай байрлалд оруулахад хангалттай. Бид зөвхөн нэмсэн хэрчим ба түүний дээр, доор байгаа шууд хөршүүдийн огтлолцлыг шалгах ёстой.
- Хэрэв хэрчим алга болвол түүнийг одоогийн жагсаалтаас хасахад хангалттай. Үүний дараа жагсаалт дахь дээд ба доод хөршүүдийн огтлолцлыг шалгах шаардлагатай.
- Жагсаалт дахь хэрчмүүдийн дарааллын өөр өөрчлөлт, тайлбарласнаас бусад нь байхгүй. Өөр ямар ч огтлолцлын шалгалт шаардлагагүй.
Эдгээр мэдэгдлийн үнэн болохыг ойлгоход дараах тэмдэглэлүүд хангалттай:
- Огтлолцолгүй хоёр хэрчим харьцангуй эрэмбээ хэзээ ч өөрчлөхгүй.
Үнэндээ хэрэв нэг хэрчим эхэндээ нөгөөгөөсөө дээгүүр байгаад дараа нь доогуур болсон бол эдгээр хоёр мөчийн хооронд эдгээр хоёр хэрчмийн огтлолцол байсан гэсэн үг. - Огтлолцдоггүй хоёр хэрчим мөн ижил $y$ координаттай байж чадахгүй.
- Эндээс хэрчим гарч ирэх мөчид бид энэ хэрчмийн хувьд дараалалд байрлалыг нь олж чадах ба энэ хэрчмийг дараалалд дахин байрлуулах шаардлагагүй болно гэдэг нь гарна: дараалал дахь бусад хэрчмийн хувьд түүний эрэмбэ өөрчлөгдөхгүй.
- Огтлолцох хоёр хэрчим тэдгээрийн огтлолцлын цэгийн мөчид дараалалд бие биенийхээ хөрш байх болно.
- Тиймээс огтлолцох хэрчмүүдийн хосыг олохын тулд шүүрдэх шулууны хөдөлгөөний явцад хэзээ нэгэн цагт дор хаяж нэг удаа бие биенийхээ хөрш байсан бүх, зөвхөн тэдгээр хэрчмийн хосуудын огтлолцлыг шалгахад хангалттай.
Нэмсэн хэрчмийг түүний дээд ба доод хөршүүдтэй нь, мөн хэрчмийг хасах үед түүний дээд ба доод хөршүүдийг (хассаны дараа тэдгээр бие биенийхээ хөрш болно) шалгахад л хангалттай болохыг анзаарахад амархан. - Шүүрдэх шулууны тогтмол байрлалд бид эхлээд энэ x координатаас эхэлж буй бүх хэрчмийг нэмэх ёстой бөгөөд зөвхөн дараа нь энд төгсөж буй бүх хэрчмийг хасах ёстойг тэмдэглэх хэрэгтэй.
Ингэснээр бид орой дээрх хэрчмүүдийн огтлолцлыг алдахгүй: өөрөөр хэлбэл хоёр хэрчим нийтлэг оройтой байх тохиолдлуудыг. - Босоо хэрчмүүд үнэндээ алгоритмын зөв байдалд нөлөөлөхгүйг анхаарна уу.
Эдгээр хэрчим нэгэн зэрэг гарч ирж, алга болдгоороо онцлог. Гэвч өмнөх тайлбараас бид бүх хэрчим эхлээд дараалалд нэмэгдэж, зөвхөн дараа нь устгагдана гэдгийг мэднэ. Тиймээс хэрэв босоо хэрчим тэр мөчид нээгдсэн өөр ямар нэг хэрчимтэй (босоо хэрчмийг оруулаад) огтлолцвол энэ нь илэрнэ.
Босоо хэрчмүүдийг дарааллын аль байрлалд байрлуулах вэ? Эцсийн эцэст босоо хэрчим нэг тодорхой $y$ координатгүй, тэр нь $y$ координатын дагуу бүхэл хэрчмээр үргэлжилнэ. Гэвч энэ хэрчмээс дурын координатыг $y$ координат болгон авч болохыг ойлгоход амархан.
Ингэснээр бүхэл алгоритм хэрчмийн хосын огтлолцол дээр $2n$-ээс олон тест хийхгүй бөгөөд хэрчмүүдийн дараалалтай $O(n)$ үйлдэл хийнэ (хэрчим бүр гарч ирэх ба алга болох үед $O(1)$ үйлдэл).
Ингэснээр алгоритмын эцсийн асимптот зан төлөв нь $O(n \log n)$ болно.
Implementation¶
We present the full implementation of the described algorithm:
const double EPS = 1E-9;
struct pt {
double x, y;
};
struct seg {
pt p, q;
int id;
double get_y(double x) const {
if (abs(p.x - q.x) < EPS)
return p.y;
return p.y + (q.y - p.y) * (x - p.x) / (q.x - p.x);
}
};
bool intersect1d(double l1, double r1, double l2, double r2) {
if (l1 > r1)
swap(l1, r1);
if (l2 > r2)
swap(l2, r2);
return max(l1, l2) <= min(r1, r2) + EPS;
}
int vec(const pt& a, const pt& b, const pt& c) {
double s = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
return abs(s) < EPS ? 0 : s > 0 ? +1 : -1;
}
bool intersect(const seg& a, const seg& b)
{
return intersect1d(a.p.x, a.q.x, b.p.x, b.q.x) &&
intersect1d(a.p.y, a.q.y, b.p.y, b.q.y) &&
vec(a.p, a.q, b.p) * vec(a.p, a.q, b.q) <= 0 &&
vec(b.p, b.q, a.p) * vec(b.p, b.q, a.q) <= 0;
}
bool operator<(const seg& a, const seg& b)
{
double x = max(min(a.p.x, a.q.x), min(b.p.x, b.q.x));
return a.get_y(x) < b.get_y(x) - EPS;
}
struct event {
double x;
int tp, id;
event() {}
event(double x, int tp, int id) : x(x), tp(tp), id(id) {}
bool operator<(const event& e) const {
if (abs(x - e.x) > EPS)
return x < e.x;
return tp > e.tp;
}
};
set<seg> s;
vector<set<seg>::iterator> where;
set<seg>::iterator prev(set<seg>::iterator it) {
return it == s.begin() ? s.end() : --it;
}
set<seg>::iterator next(set<seg>::iterator it) {
return ++it;
}
pair<int, int> solve(const vector<seg>& a) {
int n = (int)a.size();
vector<event> e;
for (int i = 0; i < n; ++i) {
e.push_back(event(min(a[i].p.x, a[i].q.x), +1, i));
e.push_back(event(max(a[i].p.x, a[i].q.x), -1, i));
}
sort(e.begin(), e.end());
s.clear();
where.resize(a.size());
for (size_t i = 0; i < e.size(); ++i) {
int id = e[i].id;
if (e[i].tp == +1) {
set<seg>::iterator nxt = s.lower_bound(a[id]), prv = prev(nxt);
if (nxt != s.end() && intersect(*nxt, a[id]))
return make_pair(nxt->id, id);
if (prv != s.end() && intersect(*prv, a[id]))
return make_pair(prv->id, id);
where[id] = s.insert(nxt, a[id]);
} else {
set<seg>::iterator nxt = next(where[id]), prv = prev(where[id]);
if (nxt != s.end() && prv != s.end() && intersect(*nxt, *prv))
return make_pair(prv->id, nxt->id);
s.erase(where[id]);
}
}
return make_pair(-1, -1);
}
The main function here is solve(), which returns the intersecting segments if exists, or $(-1, -1)$, if there are no intersections.
Checking for the intersection of two segments is carried out by the intersect () function, using an algorithm based on the oriented area of the triangle.
The queue of segments is the global variable s, a set<event>. Iterators that specify the position of each segment in the queue (for convenient removal of segments from the queue) are stored in the global array where.
Two auxiliary functions prev() and next() are also introduced, which return iterators to the previous and next elements (or end(), if one does not exist).
The constant EPS denotes the error of comparing two real numbers (it is mainly used when checking two segments for intersection).