Цэг гүдгэр олон өнцөгтөд харьяалагдахыг $O(\log N)$-д шалгах¶
Дараах бодлогыг авч үзье: танд бүхэл тоон оройтой гүдгэр олон өнцөгт ба олон асуулга өгөгдсөн. Асуулга бүр нь цэг бөгөөд түүний хувьд бид тэр нь олон өнцөгтийн дотор эсвэл зааг дээр орших эсэхийг тодорхойлох ёстой. Олон өнцөгт цагийн зүүний эсрэг эрэмбэлэгдсэн гэж үзье. Бид асуулга бүрд $O(\log n)$-д онлайнаар хариулна.
Алгоритм¶
Хамгийн бага x координаттай цэгийг сонгоё. Хэрэв ийм хэд хэдэн цэг байвал бид хамгийн бага y координаттайг нь сонгоно. Түүнийг $p_0$ гэж тэмдэглэе. Одоо олон өнцөгтийн бусад бүх цэг $p_1,\dots,p_n$ сонгосон цэгээс хэмжсэн туйлын өнцгөөрөө эрэмбэлэгдсэн байна (учир нь олон өнцөгт цагийн зүүний эсрэг эрэмбэлэгдсэн).
Хэрэв цэг олон өнцөгтөд харьяалагдаж байвал тэр нь ямар нэг $p_0, p_i, p_{i + 1}$ гурвалжинд харьяалагдана (хэрэв гурвалжнуудын зааг дээр орших бол нэгээс олонд ч байж болно). $p$ нь энэ гурвалжинд харьяалагдах бөгөөд ийм бүх гурвалжны дундаас $i$ хамгийн их байх $p_0, p_i, p_{i + 1}$ гурвалжныг авч үзье.
Нэг тусгай тохиолдол бий. $p$ нь $(p_0, p_n)$ хэрчим дээр орших. Энэ тохиолдлыг бид тусад нь шалгана. Эс бөгөөс $j \le i$ байх бүх $p_j$ цэг $p_0$-ийн хувьд $p$-ээс цагийн зүүний эсрэг байх ба бусад бүх цэг $p$-ээс цагийн зүүний эсрэг биш байна. Энэ нь бид $p_0$-ийн хувьд $p$-ээс цагийн зүүний эсрэг биш байх, мөн ийм бүх цэгийн дундаас $i$ хамгийн их байх $p_i$ цэгийг хоёртын хайлтаар олж болно гэсэн үг юм. Дараа нь бид цэг үнэхээр тодорхойлсон гурвалжинд байгаа эсэхийг шалгана.
$(a - c) \times (b - c)$-ийн тэмдэг нь $c$ цэгийн хувьд $a$ цэг $b$ цэгээс цагийн зүүний дагуу эсвэл эсрэг байгааг бидэнд хэлж өгнө. Хэрэв $(a - c) \times (b - c) > 0$ бол $a$ цэг нь $c$-ээс $b$ рүү чиглэсэн векторын баруун талд байна, өөрөөр хэлбэл $c$-ийн хувьд $b$-ээс цагийн зүүний дагуу байна гэсэн үг. Хэрэв $(a - c) \times (b - c) < 0$ бол цэг зүүн талд буюу цагийн зүүний эсрэг байна. Мөн энэ нь яг $b$ ба $c$ цэгүүдийн хоорондох шулуун дээр байна.
Алгоритм руугаа буцъя: Асуулгын $p$ цэгийг авч үзье. Эхлээд бид цэг $p_1$ ба $p_n$-ийн хооронд орших эсэхийг шалгах ёстой. Эс бөгөөс тэр нь олон өнцөгтийн хэсэг байж чадахгүйг бид аль хэдийн мэдэж байна. Үүнийг $(p_1 - p_0)\times(p - p_0)$ вектор үржвэр тэг эсвэл $(p_1 - p_0)\times(p_n - p_0)$-тэй ижил тэмдэгтэй эсэхийг, мөн $(p_n - p_0)\times(p - p_0)$ тэг эсвэл $(p_n - p_0)\times(p_1 - p_0)$-тэй ижил тэмдэгтэй эсэхийг шалгах замаар хийж болно. Дараа нь бид $p$ нь $(p_0, p_1)$ шулууны хэсэг байх тусгай тохиолдлыг боловсруулна. Дараа нь бид $p_1,\dots p_n$-ээс $p_0$-ийн хувьд $p$-ээс цагийн зүүний эсрэг биш байх сүүлчийн цэгийг хоёртын хайлтаар олж болно. Ганц $p_i$ цэгийн хувьд энэ нөхцөлийг $(p_i - p_0)\times(p - p_0) \le 0$ эсэхийг шалгах замаар шалгаж болно. Ийм $p_i$ цэгийг олсны дараа бид $p$ нь $p_0, p_i, p_{i + 1}$ гурвалжны дотор орших эсэхийг шалгах ёстой. Гурвалжинд харьяалагдах эсэхийг шалгахын тулд бид зүгээр л $|(p_i - p_0)\times(p_{i + 1} - p_0)| = |(p_0 - p)\times(p_i - p)| + |(p_i - p)\times(p_{i + 1} - p)| + |(p_{i + 1} - p)\times(p_0 - p)|$ эсэхийг шалгаж болно. Энэ нь $p_0, p_i, p_{i+1}$ гурвалжны талбай нь $p_0, p_i, p$ гурвалжин, $p_0, p, p_{i+1}$ гурвалжин ба $p_i, p_{i+1}, p$ гурвалжны талбайнуудын нийлбэртэй яг ижил хэмжээтэй эсэхийг шалгана. Хэрэв $p$ гадна байвал тэдгээр гурван гурвалжны нийлбэр гурвалжны хэмжээнээс их байна. Хэрэв дотор байвал тэнцүү байна.
Implementation¶
The function prepare will make sure that the lexicographical smallest point (smallest x value, and in ties smallest y value) will be $p_0$, and computes the vectors $p_i - p_0$.
Afterwards the function pointInConvexPolygon computes the result of a query.
We additionally remember the point $p_0$ and translate all queried points with it in order compute the correct distance, as vectors don't have an initial point.
By translating the query points we can assume that all vectors start at the origin $(0, 0)$, and simplify the computations for distances and lengths.
struct pt {
long long x, y;
pt() {}
pt(long long _x, long long _y) : x(_x), y(_y) {}
pt operator+(const pt &p) const { return pt(x + p.x, y + p.y); }
pt operator-(const pt &p) const { return pt(x - p.x, y - p.y); }
long long cross(const pt &p) const { return x * p.y - y * p.x; }
long long dot(const pt &p) const { return x * p.x + y * p.y; }
long long cross(const pt &a, const pt &b) const { return (a - *this).cross(b - *this); }
long long dot(const pt &a, const pt &b) const { return (a - *this).dot(b - *this); }
long long sqrLen() const { return this->dot(*this); }
};
bool lexComp(const pt &l, const pt &r) {
return l.x < r.x || (l.x == r.x && l.y < r.y);
}
int sgn(long long val) { return val > 0 ? 1 : (val == 0 ? 0 : -1); }
vector<pt> seq;
pt translation;
int n;
bool pointInTriangle(pt a, pt b, pt c, pt point) {
long long s1 = abs(a.cross(b, c));
long long s2 = abs(point.cross(a, b)) + abs(point.cross(b, c)) + abs(point.cross(c, a));
return s1 == s2;
}
void prepare(vector<pt> &points) {
n = points.size();
int pos = 0;
for (int i = 1; i < n; i++) {
if (lexComp(points[i], points[pos]))
pos = i;
}
rotate(points.begin(), points.begin() + pos, points.end());
n--;
seq.resize(n);
for (int i = 0; i < n; i++)
seq[i] = points[i + 1] - points[0];
translation = points[0];
}
bool pointInConvexPolygon(pt point) {
point = point - translation;
if (seq[0].cross(point) != 0 &&
sgn(seq[0].cross(point)) != sgn(seq[0].cross(seq[n - 1])))
return false;
if (seq[n - 1].cross(point) != 0 &&
sgn(seq[n - 1].cross(point)) != sgn(seq[n - 1].cross(seq[0])))
return false;
if (seq[0].cross(point) == 0)
return seq[0].sqrLen() >= point.sqrLen();
int l = 0, r = n - 1;
while (r - l > 1) {
int mid = (l + r) / 2;
int pos = mid;
if (seq[pos].cross(point) >= 0)
l = mid;
else
r = mid;
}
int pos = l;
return pointInTriangle(seq[pos], seq[pos + 1], pt(0, 0), point);
}