Giao nửa mặt phẳng (Half-plane Intersection)
Tìm phần chung của n nửa mặt phẳng trong O(n log n) bằng cách sắp theo góc và duyệt deque, xử lý song song, rỗng, không bị chặn và sai số. Ứng dụng: nhân đa giác, đường tròn nội tiếp lớn nhất, quy hoạch tuyến tính 2 biến, ô Voronoi.
Giao nửa mặt phẳng (half-plane intersection) là bài toán: cho nửa mặt phẳng, mỗi cái là tập điểm nằm về một phía của một đường thẳng, tìm phần chung của tất cả. Phần chung luôn là một đa giác lồi (có thể rỗng, suy biến thành đoạn hoặc điểm, hoặc không bị chặn). Cắt lần lượt từng nửa mặt phẳng như Sutherland-Hodgman tốn ; thuật toán sắp theo góc rồi duyệt bằng deque dưới đây chỉ tốn (và nếu các đường đã được sắp sẵn).
Bài toán xuất hiện dưới nhiều dạng: tìm nhân (kernel) của đa giác, tức vùng đứng ở đó nhìn thấy toàn bộ đa giác; tìm đường tròn nội tiếp lớn nhất của đa giác lồi; quy hoạch tuyến tính 2 biến; dựng ô Voronoi của một điểm; hoặc đơn giản là diện tích phần giao của nhiều đa giác lồi.
Ý tưởng / Trực giác
Biểu diễn. Mỗi nửa mặt phẳng là một đường thẳng có hướng đi qua điểm theo vectơ chỉ phương ; ta quy ước giữ bên trái đường thẳng:
Bất phương trình ứng với và là một điểm bất kỳ trên đường . Cạnh của đa giác lồi đi ngược chiều kim đồng hồ chính là các nửa mặt phẳng "bên trái cạnh".
Vì sao sắp theo góc. Đi dọc biên của một đa giác lồi ngược chiều kim đồng hồ, hướng của các cạnh tăng dần và quay đúng một vòng. Vậy nếu sắp các nửa mặt phẳng theo góc của , các cạnh thật sự của đáp án sẽ xuất hiện đúng theo thứ tự trên biên. Ta duyệt theo thứ tự đó và giữ một deque các nửa mặt phẳng tạo thành "chuỗi biên" hiện tại; giao điểm của hai phần tử kề nhau trong deque là một đỉnh của chuỗi.
Thêm một nửa mặt phẳng (góc lớn hơn mọi phần tử đã có):
- Nếu đỉnh cuối của chuỗi (giao của hai phần tử cuối deque) nằm ngoài thì phần tử cuối không còn đóng góp cạnh nào: bỏ nó khỏi cuối deque. Lặp lại.
- Tương tự, nếu đỉnh đầu (giao của hai phần tử đầu) nằm ngoài thì bỏ phần tử đầu. Lặp lại. Điều này xảy ra khi đã quay gần hết một vòng và "cắt" vào phần đầu chuỗi.
- Đẩy vào cuối deque.
Sau khi duyệt hết, phần đầu và phần cuối deque có thể vẫn chưa khớp nhau: dùng phần tử đầu để loại bớt phần tử cuối, và ngược lại, đúng như bước 1, 2. Cuối cùng các giao điểm của các cặp kề nhau (vòng tròn) là các đỉnh của đáp án.
Vì sao bỏ được. Khi đỉnh = giao(, ) nằm ngoài và góc của lớn hơn góc của , toàn bộ phần biên do đóng góp (đi từ về phía trước) cũng nằm ngoài , vì đi theo hướng thì ta càng đi sâu vào phía ngoài của (góc của lớn hơn). Nên dư thừa và bỏ vĩnh viễn được.
Ba trường hợp đặc biệt quyết định code có đúng hay không:
- Song song cùng hướng: chỉ giữ nửa mặt phẳng chặt hơn (cái nằm bên trong cái kia), vì giao của hai đường song song không tồn tại.
- Quay từ phần tử cuối sang một góc (gồm cả song song ngược hướng): sau khi đã bỏ các phần tử thừa mà vẫn còn khoảng trống ít nhất nửa vòng giữa phần tử cuối và , thì phần chung là rỗng. Thiếu kiểm tra này, code tính giao điểm ở "phía sai" và in ra diện tích âm vô nghĩa.
- Không bị chặn: nếu các nửa mặt phẳng không bao kín một vùng hữu hạn, chuỗi biên không khép lại được. Cách chuẩn là thêm 4 nửa mặt phẳng của một khung vuông lớn ; khi đó kết quả luôn bị chặn. Nếu lớn hơn tọa độ mọi giao điểm của các đường đã cho mà kết quả vẫn chạm khung, thì vùng thật không bị chặn.
Ví dụ chạy tay
Giao 9 nửa mặt phẳng sau (mỗi dòng là đường thẳng có hướng , giữ bên trái):
| # | Đường thẳng | Bất phương trình | Góc của |
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 | |||
| 4 | |||
| 5 | |||
| 6 | |||
| 7 | |||
| 8 | |||
| 9 |
Code thêm 4 cạnh khung (đáy, ), (phải, ), (đỉnh, ), (trái, ). Thứ tự sau khi sắp theo góc: , , , , , , (trong ngoặc là các nhóm cùng hướng). Chạy thuật toán (đây là vết in ra từ chính code bên dưới):
| Thêm | Xử lý | Deque sau bước |
|---|---|---|
| 1 | deque rỗng, đẩy vào | 1 |
| 6 | cùng hướng với 1, chặt hơn : bỏ qua 6 | 1 |
| cùng hướng với 1, lỏng hơn: bỏ qua | 1 | |
| 2 | đẩy vào; đỉnh giao(1, 2) | 1, 2 |
| cùng hướng với 2, lỏng hơn: bỏ qua | 1, 2 | |
| 9 | thỏa ; đẩy vào, đỉnh giao(2, 9) | 1, 2, 9 |
| 5 | đỉnh cuối vi phạm : bỏ 9; đỉnh thỏa, đẩy 5 | 1, 2, 5 |
| 7 | cùng hướng với 5, lỏng hơn: bỏ qua | 1, 2, 5 |
| 3 | đỉnh cuối giao(2, 5) thỏa ; đẩy vào | 1, 2, 5, 3 |
| cùng hướng với 3, lỏng hơn: bỏ qua | 1, 2, 5, 3 | |
| 8 | đỉnh cuối giao(5, 3) thỏa ; đẩy vào | 1, 2, 5, 3, 8 |
| 4 | đỉnh cuối giao(3, 8) và đỉnh đầu đều thỏa ; đẩy vào | 1, 2, 5, 3, 8, 4 |
| cùng hướng với 4, lỏng hơn: bỏ qua | 1, 2, 5, 3, 8, 4 |
Bước dọn cuối: đỉnh giao(8, 4) thỏa (phần tử đầu), đỉnh giao(1, 2) thỏa (phần tử cuối), không bỏ gì. Đáp án là lục giác có các đỉnh là giao của các cặp kề nhau, ngược chiều kim đồng hồ:
graph 6 1 2 2 3 3 4 4 5 5 6 6 1 name 1 A name 2 B name 3 C name 4 D name 5 E name 6 F label 1 (0,0) label 2 (4,0) label 3 (4,2) label 4 (2,4) label 5 (1,4) label 6 (0,3) pos 1 0 240 pos 2 240 240 pos 3 240 120 pos 4 120 0 pos 5 60 0 pos 6 0 60 highlight orange 3-4 highlight green 5-6
Cạnh cam do nửa mặt phẳng 5 () đóng góp, cạnh xanh do 8. Các nửa mặt phẳng 6, 7, 9 và cả 4 cạnh khung đều dư thừa. Diện tích: hình vuông bị cắt góc tam giác vuông cạnh (diện tích ) ở và tam giác cạnh (diện tích ) ở , còn . Chương trình in 13.500000.
Cài đặt
Dữ liệu: , rồi dòng , mỗi dòng là một nửa mặt phẳng nằm bên trái đường thẳng có hướng (tọa độ cỡ ). In diện tích phần giao bên trong khung (bằng nếu rỗng).
Góc được so sánh chính xác bằng tích có hướng: chia các hướng thành nửa trên và nửa dưới , trong cùng một nửa thì đứng trước khi . Cách này không bị sai số như atan2.
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
const ld EPS = 1e-9;
struct Pt {
ld x, y;
};
Pt operator+(Pt a, Pt b) { return {a.x + b.x, a.y + b.y}; }
Pt operator-(Pt a, Pt b) { return {a.x - b.x, a.y - b.y}; }
Pt operator*(Pt a, ld t) { return {a.x * t, a.y * t}; }
ld cross(Pt a, Pt b) { return a.x * b.y - a.y * b.x; }
ld dot(Pt a, Pt b) { return a.x * b.x + a.y * b.y; }
// Half-plane: the points on the LEFT of the directed line p -> p + d
struct HalfPlane {
Pt p, d;
// true if r lies strictly outside (to the right of the line)
bool out(Pt r) const { return cross(d, r - p) < -EPS; }
};
// Intersection point of the two boundary lines (they must not be parallel)
Pt inter(const HalfPlane& s, const HalfPlane& t) {
ld k = cross(t.p - s.p, t.d) / cross(s.d, t.d);
return s.p + s.d * k;
}
// Exact angle comparison: upper half [0, pi) first, then [pi, 2pi)
int half(Pt d) { return (d.y < 0 || (d.y == 0 && d.x < 0)) ? 1 : 0; }
bool byAngle(const HalfPlane& a, const HalfPlane& b) {
int ha = half(a.d), hb = half(b.d);
if (ha != hb) return ha < hb;
return cross(a.d, b.d) > 0;
}
// Returns the vertices (counter-clockwise) of the intersection inside the box
// [-M, M]^2; an empty vector means the intersection is empty (or degenerate).
vector<Pt> halfPlaneIntersection(vector<HalfPlane> hs, ld M) {
Pt box[4] = {{-M, -M}, {M, -M}, {M, M}, {-M, M}};
for (int i = 0; i < 4; i++) hs.push_back({box[i], box[(i + 1) % 4] - box[i]});
sort(hs.begin(), hs.end(), byAngle);
int n = hs.size();
vector<HalfPlane> dq(n + 1);
int head = 0, tail = 0; // deque is dq[head .. tail-1]
for (int i = 0; i < n; i++) {
const HalfPlane& h = hs[i];
// The last vertex of the current chain is cut off by h: drop the back
while (tail - head >= 2 && h.out(inter(dq[tail - 1], dq[tail - 2]))) tail--;
// Same for the first vertex: drop the front
while (tail - head >= 2 && h.out(inter(dq[head], dq[head + 1]))) head++;
if (tail - head >= 1 && cross(dq[tail - 1].d, h.d) < EPS) {
// Turning by 180 degrees or more from the back: empty intersection
if (cross(dq[tail - 1].d, h.d) < -EPS || dot(h.d, dq[tail - 1].d) < 0) return {};
// Same direction: keep only the more restrictive one
if (h.out(dq[tail - 1].p)) tail--;
else continue;
}
dq[tail++] = h;
}
// The last half-planes may cut off vertices at the front and vice versa
while (tail - head >= 3 && dq[head].out(inter(dq[tail - 1], dq[tail - 2]))) tail--;
while (tail - head >= 3 && dq[tail - 1].out(inter(dq[head], dq[head + 1]))) head++;
if (tail - head < 3) return {};
vector<Pt> poly;
for (int i = head; i < tail; i++)
poly.push_back(inter(dq[i], dq[i + 1 < tail ? i + 1 : head]));
return poly;
}
ld area(const vector<Pt>& poly) {
ld s = 0;
// measure from poly[0] to keep the numbers small (less rounding error)
for (size_t i = 1; i + 1 < poly.size(); i++) s += cross(poly[i] - poly[0], poly[i + 1] - poly[0]);
return s / 2;
}
int main() {
int n;
scanf("%d", &n);
vector<HalfPlane> hs(n);
for (auto& h : hs) {
double x1, y1, x2, y2; // keep the left side of (x1, y1) -> (x2, y2)
scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
h.p = {x1, y1};
h.d = Pt{x2, y2} - h.p;
}
vector<Pt> poly = halfPlaneIntersection(hs, 1e5);
printf("%.6f\n", (double)area(poly));
}
import sys
from functools import cmp_to_key
EPS = 1e-9
def cross(ax, ay, bx, by):
return ax * by - ay * bx
# A half-plane is (px, py, dx, dy): the points on the LEFT of p -> p + d
def out(h, x, y):
px, py, dx, dy = h
return cross(dx, dy, x - px, y - py) < -EPS
def inter(s, t):
# intersection of the two boundary lines (not parallel)
k = cross(t[0] - s[0], t[1] - s[1], t[2], t[3]) / cross(s[2], s[3], t[2], t[3])
return s[0] + s[2] * k, s[1] + s[3] * k
def half(h):
return 1 if h[3] < 0 or (h[3] == 0 and h[2] < 0) else 0
def by_angle(a, b):
# exact comparison of direction angles, no atan2
if half(a) != half(b):
return half(a) - half(b)
c = cross(a[2], a[3], b[2], b[3])
return -1 if c > 0 else (1 if c < 0 else 0)
def half_plane_intersection(hs, M):
box = [(-M, -M), (M, -M), (M, M), (-M, M)]
hs = hs + [(box[i][0], box[i][1], box[(i + 1) % 4][0] - box[i][0],
box[(i + 1) % 4][1] - box[i][1]) for i in range(4)]
hs.sort(key=cmp_to_key(by_angle))
dq = [None] * (len(hs) + 1)
head = tail = 0
for h in hs:
while tail - head >= 2 and out(h, *inter(dq[tail - 1], dq[tail - 2])):
tail -= 1
while tail - head >= 2 and out(h, *inter(dq[head], dq[head + 1])):
head += 1
if tail - head >= 1:
b = dq[tail - 1]
c = cross(b[2], b[3], h[2], h[3])
if c < EPS:
# turning by 180 degrees or more from the back: empty
if c < -EPS or h[2] * b[2] + h[3] * b[3] < 0:
return []
if out(h, b[0], b[1]):
tail -= 1 # h is more restrictive
else:
continue # b is more restrictive
dq[tail] = h
tail += 1
while tail - head >= 3 and out(dq[head], *inter(dq[tail - 1], dq[tail - 2])):
tail -= 1
while tail - head >= 3 and out(dq[tail - 1], *inter(dq[head], dq[head + 1])):
head += 1
if tail - head < 3:
return []
return [inter(dq[i], dq[i + 1 if i + 1 < tail else head]) for i in range(head, tail)]
def area(poly):
# measure from poly[0] to keep the numbers small (less rounding error)
s = 0.0
x0, y0 = poly[0] if poly else (0, 0)
for i in range(1, len(poly) - 1):
s += cross(poly[i][0] - x0, poly[i][1] - y0, poly[i + 1][0] - x0, poly[i + 1][1] - y0)
return s / 2
def main():
data = sys.stdin.read().split()
n = int(data[0])
hs = []
for i in range(n):
x1, y1, x2, y2 = map(float, data[1 + 4 * i: 5 + 4 * i])
hs.append((x1, y1, x2 - x1, y2 - y1))
print("%.6f" % area(half_plane_intersection(hs, 1e5)))
main()
Kiểm chứng: cả hai chương trình đã được so với cách "trâu" (cắt khung vuông bằng Sutherland-Hodgman, tính chính xác bằng phân số) trên hơn 6000 bộ ngẫu nhiên gồm đủ loại: rỗng, không bị chặn, suy biến thành đoạn thẳng, nhiều đường song song cùng hướng và ngược hướng. Với tiếp tuyến của đường tròn bán kính , code C++ chạy khoảng giây và cho diện tích (xấp xỉ ).
Ứng dụng
Nhân của đa giác (kernel, vùng quan sát). Điểm nhìn thấy toàn bộ đa giác đơn khi và chỉ khi nằm bên trong (phía trái) mọi cạnh của đi ngược chiều kim đồng hồ. Vậy nhân của là giao của nửa mặt phẳng tạo bởi các cạnh. Ví dụ hình chữ L có nhân là hình vuông , diện tích . Đa giác có nhân khác rỗng gọi là đa giác hình sao (star-shaped). Trước khi dựng, nhớ đưa đa giác về chiều ngược kim đồng hồ.
Đường tròn nội tiếp lớn nhất của đa giác lồi. Tâm của đường tròn bán kính nằm trong đa giác khi và chỉ khi cách mọi cạnh ít nhất , tức thuộc giao các nửa mặt phẳng dời vào trong một đoạn theo pháp tuyến. Giao này thu nhỏ dần khi tăng nên chặt nhị phân (xem Sắp xếp và tìm kiếm): với là số vòng chặt. Tam giác cho ; hình vuông cạnh cho .
Quy hoạch tuyến tính 2 biến. Cực đại với các ràng buộc : miền khả thi là giao nửa mặt phẳng, và một hàm tuyến tính đạt cực trị tại một đỉnh của đa giác lồi, nên chỉ cần dựng giao rồi thử mọi đỉnh. Xem thêm Quy hoạch tuyến tính cho trường hợp nhiều biến và đối ngẫu. Ví dụ bài freedream: đối ngẫu của bài toán là với , ; giao nửa mặt phẳng và lấy giá trị lớn nhất trên các đỉnh cho đúng đáp án và của hai ví dụ.
Ô Voronoi. Các điểm gần hơn là nửa mặt phẳng giới hạn bởi đường trung trực của (phía chứa ). Ô Voronoi của là giao của nửa mặt phẳng như vậy, dựng trong ; dựng cả ô mất , đủ cho vài nghìn.
Ba hàm bổ trợ (dùng chung HalfPlane, halfPlaneIntersection ở trên), đã chạy kiểm tra trên các ví dụ vừa nêu (phần quy hoạch tuyến tính còn được so với cách thử mọi cặp dự án trên 3000 bộ ngẫu nhiên):
// a*x + b*y <= c as a half-plane
HalfPlane lin(ld a, ld b, ld c) {
ld s = a * a + b * b;
return {{a * c / s, b * c / s}, {-b, a}};
}
// Shift every half-plane by r towards its inside (left normal)
HalfPlane shrink(HalfPlane h, ld r) {
ld len = sqrtl(dot(h.d, h.d));
Pt normal = {-h.d.y / len, h.d.x / len}; // unit vector pointing left
return {h.p + normal * r, h.d};
}
ld inscribedRadius(vector<Pt> poly) { // convex, counter-clockwise
vector<HalfPlane> hs;
for (size_t i = 0; i < poly.size(); i++) hs.push_back({poly[i], poly[(i + 1) % poly.size()] - poly[i]});
ld lo = 0, hi = 1e4;
for (int it = 0; it < 100; it++) {
ld r = (lo + hi) / 2;
vector<HalfPlane> sh;
for (auto& h : hs) sh.push_back(shrink(h, r));
if (!halfPlaneIntersection(sh, 1e5).empty()) lo = r; else hi = r;
}
return lo;
}
Độ phức tạp
| Bước | Thời gian | Bộ nhớ |
|---|---|---|
| Sắp xếp nửa mặt phẳng theo góc | ||
| Duyệt deque | ||
| Diện tích đáp án |
Vì sao duyệt deque là ? Mỗi nửa mặt phẳng được đẩy vào deque nhiều nhất một lần và bị lấy ra (ở đầu hoặc cuối) nhiều nhất một lần. Mỗi lần kiểm tra trong vòng while hoặc kết thúc vòng lặp, hoặc lấy ra một phần tử, nên tổng số lần kiểm tra là . Nếu các đường đã sắp theo góc sẵn (ví dụ là cạnh của vài đa giác lồi, trộn theo góc như tổng Minkowski) thì toàn bộ thuật toán là . Bộ nhớ là mảng nửa mặt phẳng và deque, .
⚠️ Lỗi thường gặp
- Thiếu kiểm tra "quay ": chỉ xử lý trường hợp song song ngược hướng là chưa đủ. Sau khi bỏ hết các phần tử thừa, nếu phần tử cuối deque và lệch nhau từ nửa vòng trở lên thì phần chung rỗng. Triệu chứng: diện tích âm hoặc đa giác "lộn ngược" trên vài test ngẫu nhiên có đáp án rỗng. Cách tránh: kiểm tra
cross(back.d, h.d) < EPSnhư trong code, trả rỗng khi góc quay . - Quên khung bao: khi vùng giao không bị chặn, deque có thể còn ít hơn 3 phần tử hoặc hai phần tử kề nhau song song, và code tính giao của hai đường song song (chia cho ). Luôn thêm 4 cạnh khung, và chọn lớn hơn mọi tọa độ có ý nghĩa của bài.
- Khung quá lớn: sai số khi tính giao điểm tỉ lệ với độ lớn tọa độ, còn sai số diện tích tỉ lệ với . Với và
double, một đáp án suy biến thành đoạn thẳng dài có thể cho "diện tích" cỡ thay vì . Chọn vừa đủ lớn, và tính shoelace so với đỉnh đầu (poly[i] - poly[0]) để giảm sai số. Lưu ýlong doubletrên ARM (Mac M1/M2...) và MSVC chỉ làdouble. - Sắp theo
atan2rồi so bằng==: hai vectơ cùng hướng nhưng khác độ dài như và có thể choatan2lệch nhau ở bit cuối, nên không được coi là song song; thứ tự giữa chúng khi đó tùy may rủi. Dùng so sánh chính xác bằng tích có hướng (như code), hoặc nếu dùngatan2thì so góc với epsilon và xử lý nhóm cùng góc. - Sai phía: quy ước "giữ bên trái" phải nhất quán. Cạnh đa giác theo chiều kim đồng hồ, hay chuyển thành thay vì , sẽ lấy nhầm phía ngoài và cho kết quả rỗng. Kiểm tra bằng một điểm chắc chắn nằm trong.
- Song song cùng hướng giữ nhầm cái lỏng hơn: phải giữ cái chặt hơn, tức cái có điểm nằm bên trong cái kia. Nếu so sánh ngược, đáp án to hơn thực tế.
- Bỏ bước dọn cuối: sau vòng lặp chính, phải dùng phần tử đầu loại các phần tử cuối thừa và ngược lại; nếu không, đáp án có thể thừa đỉnh nằm ngoài một nửa mặt phẳng ở đầu deque.
- Biên và suy biến:
outdùng nên điểm nằm trên biên được coi là ở trong; giao suy biến thành một điểm hoặc đoạn có thể trả về đa giác diện tích chứ không phải rỗng. Nếu đề hỏi "có điểm nằm thực sự bên trong không", hãy dời mọi nửa mặt phẳng vào trong một lượng nhỏ trước khi giao, hoặc kiểm tra diện tích . - Epsilon không theo tỉ lệ:
cross(d, r - p)tỉ lệ với . Nếu độ dài các vectơ chỉ phương chênh nhau nhiều (ví dụ và ), nên chuẩn hóa về độ dài hoặc chọn epsilon theo độ lớn dữ liệu.
Biến thể / Mở rộng
- nhỏ: cắt khung bằng Sutherland-Hodgman ngắn và khó sai hơn, đủ cho vài nghìn. Cũng là cách "trâu" tốt nhất để đối chiếu.
- Quy hoạch tuyến tính 2 biến kỳ vọng: thuật toán gia tăng ngẫu nhiên của Seidel chỉ tìm điểm tối ưu, không dựng cả đa giác (xem Thuật toán ngẫu nhiên).
- Đối ngẫu với bao lồi: biên dưới của các đường (giao các nửa mặt phẳng ) tương ứng với bao lồi trên của các điểm . Đây là cùng ý tưởng với bao lồi và Li Chao Tree cho truy vấn min của các đường thẳng.
- Kiểm tra điểm: sau khi có đa giác lồi kết quả, kiểm tra một điểm có thuộc vùng hay không bằng kiểm tra điểm trong đa giác . Hàm một biến lồi trên vùng (ví dụ khoảng cách) có thể kết hợp chặt tam phân. Các kỹ thuật nền tảng khác ở Hình học.
Bài tập luyện
Kho bài CTOJ hiện chưa có bài nào bắt buộc giao với hàng chục nghìn đường thẳng tổng quát; các bài dưới đây đi từ giao các nửa mặt phẳng đặc biệt tới quy hoạch tuyến tính 2 biến, nơi thuật toán trên là một lời giải đúng.
- Cánh đồng ngô của Vasya (cornfield): (Trung bình) Cánh đồng hình vuông xoay là giao của 4 nửa mặt phẳng; luyện cách viết mỗi cạnh thành bất phương trình đúng phía.
- Robot Breakout (robotbrk): (Khó) Mỗi robot thiếu hành động cho một nửa mặt phẳng song song trục; giao của chúng là một hình chữ nhật, minh họa quy tắc "cùng hướng thì giữ cái chặt hơn" và khung bao .
- Hình chữ nhật quay (rectpzl): (Rất khó) Diện tích giao của hình chữ nhật và bản xoay của nó: giao 8 nửa mặt phẳng rồi tính shoelace, cẩn thận sai số khi kích thước tới và khi góc bằng hay (các cạnh song song).
- Giấc mơ freelancer (freedream): (Chuyên gia) Đối ngẫu thành quy hoạch tuyến tính 2 biến với ; giao nửa mặt phẳng và thử các đỉnh.
- Giấc mơ nghề nghiệp (thhv19clc10_b): (Chuyên gia) Cùng mô hình với
freedreamnhưng : thuật toán vẫn kịp, so sánh với lời giải bao lồi trên các điểm (chính là phía đối ngẫu).
Bình luận