Geometry

Tích có hướng

Với $\vec u = (x_1, y_1)$, $\vec v = (x_2, y_2)$, tích có hướng $\vec u \times \vec v = x_1 y_2 - y_1 x_2$. Với ba điểm, $\operatorname{cross}(A, B, C) = (B - A) \times (C - A)$ dương khi $C$ nằm bên trái đường có hướng $A \to B$ (quay ngược chiều kim đồng hồ), âm khi bên phải, bằng 0 khi thẳng hàng. Giá trị tuyệt đối là hai lần diện tích tam giác $ABC$.

Tọa độ tới $10^9$ thì hiệu tới $2 \cdot 10^9$, mỗi tích tới $4 \cdot 10^{18}$, hiệu hai tích tới $8 \cdot 10^{18}$: vẫn vừa long long (tới khoảng $9{,}2 \cdot 10^{18}$) nhưng sát giới hạn. Ép kiểu sang long long trước khi nhân; tọa độ lớn hơn thì dùng __int128. Chỉ cần dấu của kết quả nên không có chia hay căn, không có sai số.

Trong hình, kéo $A$, $B$, $C$: dấu của tích có hướng cho biết $C$ ở bên trái, bên phải hay trên đường $A \to B$.

Giao hai đoạn thẳng

Hai đoạn $AB$, $CD$ cắt nhau “thật sự” khi $C$, $D$ ở hai phía của đường $AB$ và $A$, $B$ ở hai phía của đường $CD$: $d_1 = \operatorname{cross}(A, B, C)$ và $d_2 = \operatorname{cross}(A, B, D)$ trái dấu, tương tự $d_3, d_4$.

Các trường hợp còn lại là có một tích bằng 0: điểm đó thẳng hàng với đoạn kia, và chung điểm khi nó nằm trong hộp bao của đoạn kia. Kiểm đủ bốn điểm như vậy là phủ hết, kể cả hai đoạn cùng nằm trên một đường thẳng. So dấu bằng cách so từng tích với 0, đừng nhân $d_1 \cdot d_2$ vì tràn số.

Trong hình, kéo bốn đầu mút; thử cả trường hợp một đầu nằm đúng trên đoạn kia.

Ví dụHai Đoạn Có Gặp Nhau?

Đề. $t \le 10^5$ cặp đoạn thẳng đóng, tọa độ tới $10^9$. Cho biết hai đoạn có điểm chung không.

Lời giải. Hai đoạn cắt nhau thật sự khi mỗi đoạn có hai đầu nằm ở hai phía của đường thẳng chứa đoạn kia. Còn lại chỉ có thể chung điểm khi một đầu mút thẳng hàng với đoạn kia và nằm trong hộp bao của nó; kiểm đủ bốn đầu mút như vậy là phủ mọi trường hợp chạm, kể cả hai đoạn chồng nhau trên cùng một đường thẳng.

Bước 1: so dấu. sgn trả $-1$, $0$, $1$. So dấu bằng d1 * d2 < 0 trên các số đã lấy dấu, không nhân hai tích có hướng thật vì sẽ tràn.

int d1 = sgn(cross(ax, ay, bx, by, cx, cy)), d2 = sgn(cross(ax, ay, bx, by, dx, dy));
int d3 = sgn(cross(cx, cy, dx, dy, ax, ay)), d4 = sgn(cross(cx, cy, dx, dy, bx, by));
bool ok = d1 * d2 < 0 && d3 * d4 < 0;

Bước 2: trường hợp chạm. onSeg(A, B, P) chỉ kiểm $P$ có nằm trong hộp bao của $AB$; nó được gọi khi tích có hướng bằng 0, tức $P$ thẳng hàng với $AB$. Thẳng hàng và trong hộp bao nghĩa là nằm trên đoạn.

if (!d1 && onSeg(ax, ay, bx, by, cx, cy)) ok = 1;
if (!d2 && onSeg(ax, ay, bx, by, dx, dy)) ok = 1;
if (!d3 && onSeg(cx, cy, dx, dy, ax, ay)) ok = 1;
if (!d4 && onSeg(cx, cy, dx, dy, bx, by)) ok = 1;

Hai đoạn cùng nằm trên một đường mà rời nhau: cả bốn tích bằng 0 nhưng không đầu mút nào trong hộp bao của đoạn kia, kết quả NO.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll cross(ll ax, ll ay, ll bx, ll by, ll cx, ll cy) {
    return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax);
}

int sgn(ll x) {
    return (x > 0) - (x < 0);
}

bool onSeg(ll ax, ll ay, ll bx, ll by, ll px, ll py) {
    return min(ax, bx) <= px && px <= max(ax, bx) && min(ay, by) <= py && py <= max(ay, by);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        ll ax, ay, bx, by, cx, cy, dx, dy;
        cin >> ax >> ay >> bx >> by >> cx >> cy >> dx >> dy;
        int d1 = sgn(cross(ax, ay, bx, by, cx, cy)), d2 = sgn(cross(ax, ay, bx, by, dx, dy));
        int d3 = sgn(cross(cx, cy, dx, dy, ax, ay)), d4 = sgn(cross(cx, cy, dx, dy, bx, by));
        bool ok = d1 * d2 < 0 && d3 * d4 < 0;
        if (!d1 && onSeg(ax, ay, bx, by, cx, cy)) ok = 1;
        if (!d2 && onSeg(ax, ay, bx, by, dx, dy)) ok = 1;
        if (!d3 && onSeg(cx, cy, dx, dy, ax, ay)) ok = 1;
        if (!d4 && onSeg(cx, cy, dx, dy, bx, by)) ok = 1;
        cout << (ok ? "YES" : "NO") << '\n';
    }
}

ChạyInput5
0 0 4 4 0 4 4 0
0 0 4 0 4 0 7 3
0 0 6 0 2 0 8 0
0 0 2 0 3 0 5 0
-2 -2 2 2 0 0 0 5

OutputYES
YES
YES
NO
YES

Mỗi cặp $O(1)$.

Diện tích và Pick

Công thức dây giày: với đa giác đơn $P_1, \dots, P_n$, hai lần diện tích có dấu là $\sum_i P_i \times P_{i+1}$ (với $P_{n+1} = P_1$); dương khi các đỉnh đi ngược chiều kim đồng hồ. Với tọa độ nguyên, hai lần diện tích là số nguyên, nên in nó để khỏi số thực.

Hình dưới cho kéo các đỉnh trên lưới: diện tích tính bằng dây giày, số điểm biên bằng tổng gcd các cạnh, phần còn lại là số điểm bên trong.

Định lý Pick: đa giác đơn có đỉnh nguyên thỏa $A = I + B/2 - 1$, với $I$ là số điểm nguyên bên trong, $B$ là số điểm nguyên trên biên. Cạnh từ $P$ tới $Q$ chứa $\gcd(|Q_x - P_x|, |Q_y - P_y|)$ điểm nguyên không tính một đầu, nên $B$ là tổng các $\gcd$ đó; suy ra $I = (2A - B + 2)/2$.

Ví dụDiện Tích Gấp Đôi

Đề. Đa giác đơn $n \le 1000$ đỉnh, tọa độ tới $10^9$. In hai lần diện tích.

Lời giải. Công thức dây giày: hai lần diện tích có dấu là $\sum_i (x_i y_{i+1} - x_{i+1} y_i)$, với đỉnh sau đỉnh cuối là đỉnh đầu. Dấu phụ thuộc chiều đi của các đỉnh, nên lấy trị tuyệt đối.

Mỗi số hạng tới $2 \cdot 10^{18}$, cộng $1000$ số hạng có thể vượt long long giữa chừng dù kết quả cuối thì không, nên cộng bằng __int128. Ép từng thừa số trước khi nhân; viết (__int128)(x[i] * y[j]) là sai, vì phép nhân đã tràn trong long long trước khi ép.

for (int i = 0; i < n; i++) {
    int j = (i + 1) % n;
    s += (__int128)x[i] * y[j] - (__int128)x[j] * y[i];
}

Kết quả không quá $8 \cdot 10^{18}$, nên ép về long long để in. Dùng __int128 có đắt không?

__int128 chỉ chậm hơn long long khoảng 10%, vì thời gian chủ yếu dành cho đọc bộ nhớ. Quy tắc: nghi ngờ tràn thì cứ dùng __int128, cái giá rất nhỏ.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll n, x[1005], y[1005];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
    __int128 s = 0;
    for (int i = 0; i < n; i++) {
        int j = (i + 1) % n;
        s += (__int128)x[i] * y[j] - (__int128)x[j] * y[i];
    }
    if (s < 0) s = -s;
    cout << (ll)s << '\n';
}

ChạyInput4
0 0
0 4
4 4
4 0

Output32

$O(n)$.

Điểm trong đa giác

Bắn tia từ điểm $P$ sang phải; $P$ ở trong khi tia cắt biên một số lẻ lần. Đếm cạnh $(A, B)$ có đúng một đầu nằm cao hơn $P$ (quy ước nửa mở (A.y > P.y) != (B.y > P.y) để đỉnh nằm đúng độ cao của tia chỉ được đếm một lần) và $P$ nằm bên trái giao điểm. Điều kiện “bên trái” kiểm bằng dấu tích có hướng, không cần chia: cạnh đi lên ($A_y < B_y$) thì $P$ bên trái khi $\operatorname{cross}(A, B, P) > 0$, cạnh đi xuống thì ngược lại.

Trước khi đếm, kiểm $P$ có nằm trên một cạnh (thẳng hàng và trong hộp bao) để trả lời “trên biên”. Mỗi truy vấn $O(n)$.

Trong hình, cạnh cam là cạnh bị đếm. Kéo $P$ qua các đỉnh lõm để thấy số lần cắt đổi chẵn lẻ.

Ví dụBa Miền Của Đa Giác

Đề. Đa giác đơn $n \le 1000$ đỉnh, $m \le 1000$ điểm truy vấn, tọa độ tới $10^9$. In INSIDE, OUTSIDE hoặc BOUNDARY.

Lời giải. Với mỗi điểm $P$: trước hết kiểm $P$ có nằm trên cạnh nào không. Nếu không, bắn tia từ $P$ sang phải và đếm số cạnh cắt tia; lẻ là ở trong.

Bước 1: trên biên. Tích có hướng bằng 0 và nằm trong hộp bao của cạnh. Biên được ưu tiên khi in, nên điểm trên cạnh không bị xếp nhầm vì phép đếm chẵn lẻ.

if (!c && min(x[i], x[j]) <= px && px <= max(x[i], x[j]) && min(y[i], y[j]) <= py && py <= max(y[i], y[j])) boundary = 1;

Bước 2: tia sang phải. (y[i] > py) != (y[j] > py): cạnh có đúng một đầu nằm hẳn phía trên tia. Đầu nằm đúng trên tia được coi là “không cao hơn”, nên khi tia đi qua một đỉnh, chỉ một trong hai cạnh kề được đếm (hoặc cả hai không, nếu đỉnh là chỗ lồi lên hay lõm xuống), đúng như số lần tia thật sự đi xuyên biên. (y[i] < y[j]) == (c > 0): cạnh đi lên thì $P$ ở bên trái giao điểm khi $P$ ở bên trái cạnh; cạnh đi xuống thì ngược lại.

if ((y[i] > py) != (y[j] > py) && ((y[i] < y[j]) == (c > 0))) inside = !inside;

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int n, m;
ll x[1005], y[1005];

ll cross(ll ax, ll ay, ll bx, ll by, ll cx, ll cy) {
    return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
    while (m--) {
        ll px, py;
        cin >> px >> py;
        bool boundary = 0, inside = 0;
        for (int i = 0; i < n; i++) {
            int j = (i + 1) % n;
            ll c = cross(x[i], y[i], x[j], y[j], px, py);
            if (!c && min(x[i], x[j]) <= px && px <= max(x[i], x[j]) && min(y[i], y[j]) <= py && py <= max(y[i], y[j])) boundary = 1;
            if ((y[i] > py) != (y[j] > py) && ((y[i] < y[j]) == (c > 0))) inside = !inside;
        }
        cout << (boundary ? "BOUNDARY" : inside ? "INSIDE" : "OUTSIDE") << '\n';
    }
}

+13 dòngChạyInput6 6
0 0
8 0
8 6
5 6
5 2
0 2
1 1
6 4
3 4
5 4
8 6
-1 1

OutputINSIDE
INSIDE
OUTSIDE
BOUNDARY
BOUNDARY
OUTSIDE

Mỗi điểm $O(n)$, tổng $O(nm)$.

Bao lồi

Chuỗi đơn điệu (Andrew): sắp các điểm theo $(x, y)$. Dựng nửa dưới bằng cách duyệt từ trái sang phải với một ngăn xếp: khi điểm mới làm ba điểm cuối quay phải, bỏ điểm giữa. Dựng nửa trên tương tự khi duyệt ngược lại. Ghép hai nửa, bỏ điểm đầu mút bị lặp. Tổng $O(n \log n)$ do sắp xếp.

Điều kiện bỏ quyết định số điểm thẳng hàng trên biên: bỏ khi tích có hướng âm thì giữ mọi điểm biên, bỏ khi không dương thì chỉ giữ các đỉnh. Đề đòi mọi điểm trên biên thì dùng điều kiện thứ nhất.

Trong hình, xanh lá là ngăn xếp hiện tại, cam là điểm đang xét, đỏ là điểm vừa bị bỏ. Bật giữ điểm thẳng hàng để so hai điều kiện bỏ.

Ví dụĐường Biên Ngoài Cùng

Đề. $n \le 2 \cdot 10^5$ điểm phân biệt, không thẳng hàng hết. In mọi điểm nằm trên biên bao lồi.

Lời giải. Chuỗi đơn điệu của Andrew. Sắp các điểm theo $(x, y)$; nửa dưới duyệt từ trái sang phải, nửa trên duyệt từ phải sang trái, mỗi nửa giữ một ngăn xếp và bỏ điểm giữa khi ba điểm cuối quay phải. Đề đòi mọi điểm trên biên, nên chỉ bỏ khi tích có hướng âm, giữ các điểm thẳng hàng.

Bước 1: nửa dưới. Điểm mới làm cross(lo[-2], lo[-1], p) < 0 thì lo[-1] nằm phía trong, bỏ. Bỏ xong mới đẩy điểm mới vào.

for (int i = 0; i < n; i++) {
    while (lo.size() >= 2 && cross(lo[lo.size() - 2], lo.back(), p[i]) < 0) lo.pop_back();
    lo.push_back(p[i]);
}

Bước 2: nửa trên cùng vòng đó nhưng duyệt ngược. Hai nửa có chung hai đầu mút (điểm nhỏ nhất và lớn nhất), nên mỗi nửa bỏ điểm cuối trước khi ghép; ghép lo rồi hi được biên theo chiều ngược kim đồng hồ.

lo.pop_back(), hi.pop_back();

Đề bảo đảm các điểm không thẳng hàng hết. Nếu thẳng hàng hết, giữ điểm thẳng hàng sẽ làm hai nửa trùng nhau và mỗi điểm bị in hai lần.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int n;
vector<pair<ll, ll>> p;

ll cross(pair<ll, ll> a, pair<ll, ll> b, pair<ll, ll> c) {
    return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    p.resize(n);
    for (int i = 0; i < n; i++) cin >> p[i].first >> p[i].second;
    sort(p.begin(), p.end());
    vector<pair<ll, ll>> lo, hi;
    for (int i = 0; i < n; i++) {
        while (lo.size() >= 2 && cross(lo[lo.size() - 2], lo.back(), p[i]) < 0) lo.pop_back();
        lo.push_back(p[i]);
    }
    for (int i = n - 1; i >= 0; i--) {
        while (hi.size() >= 2 && cross(hi[hi.size() - 2], hi.back(), p[i]) < 0) hi.pop_back();
        hi.push_back(p[i]);
    }
    lo.pop_back(), hi.pop_back();
    cout << lo.size() + hi.size() << '\n';
    for (int i = 0; i < (int)lo.size(); i++) cout << lo[i].first << ' ' << lo[i].second << '\n';
    for (int i = 0; i < (int)hi.size(); i++) cout << hi[i].first << ' ' << hi[i].second << '\n';
}

ChạyInput9
0 0
2 0
4 0
4 3
2 3
0 3
2 1
1 2
3 2

Output6
0 0
2 0
4 0
4 3
2 3
0 3

Sắp $O(n \log n)$, mỗi điểm vào và ra mỗi ngăn xếp tối đa một lần.

Cặp điểm gần nhất

Sắp điểm theo $x$, quét từ trái sang phải và giữ trong set (sắp theo $y$) các điểm có hoành độ cách điểm hiện tại không quá $d$, với $d$ là khoảng cách nhỏ nhất tìm được tới giờ. Điểm mới chỉ cần so với các điểm trong set có tung độ trong $[y - d, y + d]$: trong hình chữ nhật $d \times 2d$ đó, các điểm đôi một cách nhau ít nhất $d$ nên chỉ có hằng số điểm. Tổng $O(n \log n)$.

Giữ $d^2$ dạng số nguyên, $d$ dùng để cắt cửa sổ lấy bằng căn làm tròn lên.

Trong hình, dải xanh là các điểm trong set ($x$ cách không quá $d$); khung cam là dải $y \pm d$, chỉ các điểm xanh lá trong đó được so.

Ví dụBình Phương Khoảng Cách Gần Nhất

Đề. $n \le 2 \cdot 10^5$ điểm phân biệt, tọa độ tới $10^9$. In bình phương khoảng cách nhỏ nhất giữa hai điểm.

Lời giải. Sắp theo $x$ rồi quét. set chứa các điểm đã qua có hoành độ cách điểm hiện tại không quá $d$, sắp theo $y$; $d$ là khoảng cách nhỏ nhất tìm được tới giờ. Điểm mới chỉ cần so với các điểm trong set có tung độ trong $[y - d, y + d]$. Những điểm đó nằm trong hình chữ nhật $d \times 2d$ và đôi một cách nhau ít nhất $d$, nên chỉ có hằng số điểm.

Bước 1: cửa sổ theo $x$. best là bình phương khoảng cách nhỏ nhất, giữ dạng nguyên (tới $8 \cdot 10^{18}$, vừa long long). d là căn làm tròn lên, chỉ dùng để cắt cửa sổ, nên lấy rộng hơn một chút không làm sai. Con trỏ j xóa các điểm có hoành độ kém điểm hiện tại hơn d; mỗi điểm vào và ra một lần.

ll d = (ll)sqrtl((long double)best) + 1;
while (p[i].first - p[j].first > d) s.erase({p[j].second, p[j].first}), j++;

Bước 2: dải theo $y$. set lưu cặp $(y, x)$ để sắp theo $y$; lower_bound nhảy tới điểm đầu tiên có tung độ $\ge y - d$, rồi duyệt tới khi vượt $y + d$.

set<pair<ll, ll>>::iterator it = s.lower_bound({p[i].second - d, LLONG_MIN});
for (; it != s.end() && it->first <= p[i].second + d; it++) {
    ll dx = p[i].first - it->second, dy = p[i].second - it->first;
    best = min(best, dx * dx + dy * dy);
}

Lúc đầu best = LLONG_MAX nên cửa sổ chứa mọi điểm; sau vài cặp best nhỏ đi và cửa sổ hẹp lại.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int n;
vector<pair<ll, ll>> p;
set<pair<ll, ll>> s;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    p.resize(n);
    for (int i = 0; i < n; i++) cin >> p[i].first >> p[i].second;
    sort(p.begin(), p.end());
    ll best = LLONG_MAX;
    int j = 0;
    for (int i = 0; i < n; i++) {
        ll d = (ll)sqrtl((long double)best) + 1;
        while (p[i].first - p[j].first > d) s.erase({p[j].second, p[j].first}), j++;
        set<pair<ll, ll>>::iterator it = s.lower_bound({p[i].second - d, LLONG_MIN});
        for (; it != s.end() && it->first <= p[i].second + d; it++) {
            ll dx = p[i].first - it->second, dy = p[i].second - it->first;
            best = min(best, dx * dx + dy * dy);
        }
        s.insert({p[i].second, p[i].first});
    }
    cout << best << '\n';
}

ChạyInput5
0 0
7 7
3 4
10 1
4 4

Output1

$O(n \log n)$.