Bao lồi nâng cao và kỹ thuật xoay compa

Mức độ: Chuyên sâu

Bài Diện tích đa giác và điểm nguyên đã giới thiệu bao lồi và thuật toán chuỗi đơn điệu. Bài này đi tiếp: dựng bao lồi đúng trong mọi trường hợp đặc biệt, rồi khai thác bao lồi bằng kỹ thuật xoay compa (rotating calipers) để giải các bài “xa nhất, hẹp nhất, lớn nhất” chỉ trong thời gian tuyến tính, và các thao tác trên đa giác lồi: tìm điểm, cắt, giao, cộng.

Các bạn cần nắm vững bài Điểm, khoảng cách và tích có hướng và bài Diện tích đa giác.

Bao lồi trong mọi trường hợp

Ký hiệu cross(O, A, B) là tích có hướng của OA và OB: dương nếu B nằm bên trái tia OA, âm nếu bên phải, bằng 0 nếu thẳng hàng.

Python

def cross(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def bao_loi(p, giu_thang_hang=False):
    """Các đỉnh theo chiều ngược kim đồng hồ, bắt đầu từ điểm có (x, y) nhỏ nhất."""
    p = sorted(set(p))                     # bỏ điểm trùng
    if len(p) <= 2:
        return p
    def nua(ds):
        h = []
        for q in ds:
            while len(h) >= 2:
                c = cross(h[-2], h[-1], q)
                if c < 0 or (c == 0 and not giu_thang_hang):
                    h.pop()
                else:
                    break
            h.append(q)
        return h
    duoi, tren = nua(p), nua(p[::-1])
    if giu_thang_hang and len(duoi) == len(p):   # mọi điểm thẳng hàng
        return p
    return duoi[:-1] + tren[:-1]

print(bao_loi([(0, 0), (2, 0), (2, 2), (0, 2), (1, 1), (1, 0)]))
# [(0, 0), (2, 0), (2, 2), (0, 2)]
print(bao_loi([(0, 0), (2, 0), (2, 2), (0, 2), (1, 1), (1, 0)], True))
# [(0, 0), (1, 0), (2, 0), (2, 2), (0, 2)]

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Diem {
    long long x, y;
    bool operator<(const Diem &o) const { return x < o.x || (x == o.x && y < o.y); }
    bool operator==(const Diem &o) const { return x == o.x && y == o.y; }
};

long long cross(const Diem &o, const Diem &a, const Diem &b) {
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

vector<Diem> baoLoi(vector<Diem> p, bool giuThangHang = false) {
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());   // bỏ điểm trùng
    int n = p.size();
    if (n <= 2) return p;
    auto nua = [&](const vector<Diem> &ds) {
        vector<Diem> h;
        for (const Diem &q : ds) {
            while (h.size() >= 2) {
                long long c = cross(h[h.size() - 2], h.back(), q);
                if (c < 0 || (c == 0 && !giuThangHang)) h.pop_back();
                else break;
            }
            h.push_back(q);
        }
        return h;
    };
    vector<Diem> duoi = nua(p);
    vector<Diem> nguoc(p.rbegin(), p.rend());
    vector<Diem> tren = nua(nguoc);
    if (giuThangHang && (int)duoi.size() == n) return p;   // mọi điểm thẳng hàng
    duoi.pop_back();
    tren.pop_back();
    duoi.insert(duoi.end(), tren.begin(), tren.end());
    return duoi;
}

int main() {
    vector<Diem> p = {{0, 0}, {2, 0}, {2, 2}, {0, 2}, {1, 1}, {1, 0}};
    for (auto &d : baoLoi(p)) cout << d.x << " " << d.y << endl;
    return 0;
}

Ba chỗ hay sai:

Trường hợp	Cách xử lý
Điểm trùng nhau	Bỏ trùng sau khi sắp xếp
Mọi điểm thẳng hàng	Bỏ điểm thẳng hàng thì còn 2 đầu mút; giữ điểm thẳng hàng thì nửa dưới đã chứa tất cả, trả về luôn
Cần giữ điểm nằm giữa cạnh	Chỉ bỏ khi tích có hướng nhỏ hơn 0

Lưu ý: với tọa độ tới 10⁹, tích có hướng tới 8 × 10¹⁸, sát giới hạn long long (khoảng 9,2 × 10¹⁸). Không cộng dồn các tích có hướng (ví dụ tính diện tích) nếu tọa độ lớn như vậy.

Sắp xếp theo góc chính xác

Nhiều thuật toán cần sắp các điểm theo góc quanh một tâm. Dùng atan2 thì hai hướng rất gần nhau có thể cho cùng một số thực. So sánh chính xác bằng số nguyên:

1. Chia mặt phẳng thành nửa trên (y lớn hơn 0, hoặc y = 0 và x lớn hơn 0) và nửa dưới. Nửa trên đứng trước.
2. Trong cùng một nửa, a đứng trước b khi tích có hướng a × b lớn hơn 0.

Bước 1 là bắt buộc: trên cả mặt phẳng, “a × b lớn hơn 0” không có tính bắc cầu (đi hết một vòng sẽ quay lại).

Xoay compa

Hãy tưởng tượng kẹp bao lồi giữa hai đường thẳng song song (hai càng của compa) rồi xoay một vòng. Mỗi lần một càng áp sát một cạnh (i, i + 1), càng kia chạm vào đỉnh j xa cạnh đó nhất. Quan sát quan trọng:

Khi i đi quanh bao lồi theo chiều ngược kim đồng hồ, đỉnh xa nhất j cũng chỉ đi tới, không bao giờ lùi.

Vậy chỉ cần hai con trỏ i, j cùng đi một vòng: tổng h bước thay vì h².

Python

def duong_kinh2(h):
    """Bình phương khoảng cách lớn nhất giữa hai đỉnh của đa giác lồi h (ngược chiều kim đồng hồ)."""
    d2 = lambda a, b: (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
    k = len(h)
    if k <= 2:
        return d2(h[0], h[-1])
    tot, j = 0, 1
    for i in range(k):
        ni = (i + 1) % k
        while abs(cross(h[i], h[ni], h[(j + 1) % k])) > abs(cross(h[i], h[ni], h[j])):
            j = (j + 1) % k            # j tiến tới đỉnh xa cạnh (i, ni) nhất
        tot = max(tot, d2(h[i], h[j]), d2(h[ni], h[j]))
    return tot

C++

long long d2(const Diem &a, const Diem &b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

// Bình phương khoảng cách lớn nhất giữa hai đỉnh của đa giác lồi h (ngược chiều kim đồng hồ)
long long duongKinh2(const vector<Diem> &h) {
    int k = h.size();
    if (k <= 2) return d2(h[0], h[k - 1]);
    long long tot = 0;
    int j = 1;
    for (int i = 0; i < k; i++) {
        int ni = (i + 1) % k;
        while (llabs(cross(h[i], h[ni], h[(j + 1) % k])) > llabs(cross(h[i], h[ni], h[j])))
            j = (j + 1) % k;           // j tiến tới đỉnh xa cạnh (i, ni) nhất
        tot = max(tot, max(d2(h[i], h[j]), d2(h[ni], h[j])));
    }
    return tot;
}

Cùng một khung cho nhiều bài:

Bài toán	Ở mỗi cạnh (i, i + 1) cần	Kết quả
Đường kính (hai điểm xa nhất)	đỉnh j xa cạnh nhất	lớn nhất của khoảng cách j tới hai đầu cạnh
Bề rộng (khe hẹp nhất)	đỉnh j xa cạnh nhất	nhỏ nhất của khoảng cách từ j tới cạnh
Hình chữ nhật bao nhỏ nhất	thêm hai đỉnh có hình chiếu lên hướng cạnh lớn nhất, nhỏ nhất	rộng × dài (hoặc chu vi) nhỏ nhất
Tam giác lớn nhất	cố định i, cho j chạy, đỉnh thứ ba k chỉ tiến	h2 thay vì h3

Hai định lý đứng sau bảng trên: bề rộng nhỏ nhất và hình chữ nhật bao nhỏ nhất đều đạt khi một cạnh nằm trên một cạnh của bao lồi. Vì thế chỉ cần xét h hướng.

Điểm trong đa giác lồi: tìm kiếm nhị phân

Với đa giác lồi h₀, h₁, …, h_{n - 1} (ngược chiều kim đồng hồ), các tia từ h₀ chia đa giác thành n - 2 tam giác hình quạt. Điểm P:

1. Nằm ngoài nếu ở bên phải tia h₀h₁ hoặc bên trái tia h₀h_{n - 1}.
2. Tìm nhị phân tam giác (h₀, h_i, h_{i + 1}) chứa hướng của P.
3. Xét P với cạnh h_ih_{i + 1} để kết luận trong, trên biên hay ngoài.

Mỗi câu hỏi log n bước, thay vì n bước khi xét từng cạnh.

Cắt đa giác lồi

Giữ phần của đa giác lồi nằm bên trái đường thẳng có hướng AB: đi qua từng cạnh (P, Q),

• giữ P nếu P nằm bên trái hoặc trên đường thẳng;
• nếu P và Q ở hai phía, thêm giao điểm (tỉ lệ t = c_P / (c_P - c_Q), với c là tích có hướng).

Kết quả vẫn là đa giác lồi. Từ thao tác này:

• Giao hai đa giác lồi = cắt đa giác thứ nhất lần lượt bởi mọi cạnh của đa giác thứ hai.
• Giao các nửa mặt phẳng = bắt đầu từ một hình vuông thật lớn, cắt lần lượt bởi từng nửa mặt phẳng.

Tổng Minkowski

Tổng Minkowski P + Q gồm mọi điểm p + q (cộng tọa độ). Với P, Q lồi, P + Q cũng lồi, và các cạnh của P + Q chính là các cạnh của P và Q, xếp theo góc. Bắt đầu từ tổng hai đỉnh thấp nhất, trộn hai dãy cạnh như trộn hai dãy đã sắp xếp (so sánh góc bằng tích có hướng): n + m bước.

Ví dụ: hình vuông + hình tròn bán kính r (coi như đa giác nhiều cạnh) cho hình vuông “bo góc”, chu vi tăng thêm 2πr. Đó chính là lý do sợi dây bao quanh các giếng tròn dài hơn chu vi bao lồi đúng 2πr.

Luyện tập

Gồm 20 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Dựng bao lồi trong mọi trường hợp

Bài 1. In bao lồi

Dòng đầu là n (1 ≤ n ≤ 10⁵), n dòng sau là tọa độ nguyên các điểm (|x|, |y| ≤ 10⁹, có thể trùng nhau, có thể thẳng hàng hết). In ra số đỉnh h của bao lồi, rồi h dòng là các đỉnh theo chiều ngược kim đồng hồ, bắt đầu từ đỉnh có x nhỏ nhất (nếu bằng nhau thì y nhỏ nhất). Không in các điểm nằm giữa một cạnh. Nếu mọi điểm thẳng hàng thì bao lồi là đoạn thẳng, in hai đầu mút; nếu mọi điểm trùng nhau thì in một điểm.

Ví dụ:

Nhập	In ra
6 0 0 2 0 2 2 0 2 1 1 1 0	4 0 0 2 0 2 2 0 2

Kiểm tra: nhập

8
3 1
-2 4
0 0
5 5
-1 -3
4 -2
0 6
2 2

Xem đáp số

5
-2 4
-1 -3
4 -2
5 5
0 6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Số điểm trên biên

Dòng đầu là n (1 ≤ n ≤ 10⁵), n dòng sau là tọa độ nguyên các điểm khác nhau (|x|, |y| ≤ 10⁹). In ra số điểm nằm trên biên bao lồi (kể cả các điểm nằm giữa một cạnh).

Ví dụ:

Nhập	In ra
6 0 0 2 0 2 2 0 2 1 1 1 0	5

Kiểm tra: nhập

9
0 0
3 0
6 0
6 3
6 6
3 3
0 6
2 4
1 1

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Sắp xếp theo góc

Dòng đầu là n (1 ≤ n ≤ 10⁵), n dòng sau là tọa độ nguyên các điểm khác gốc O (|x|, |y| ≤ 10⁹). Sắp xếp các điểm theo góc tạo bởi tia Ox và tia từ O đến điểm, đo ngược chiều kim đồng hồ trong khoảng [0°, 360°); điểm cùng góc thì điểm gần O hơn đứng trước. In ra các điểm theo thứ tự đó.

Ví dụ:

Nhập	In ra
5 1 1 -1 0 2 0 0 -3 2 2	2 0 1 1 2 2 -1 0 0 -3

Kiểm tra: nhập

6
3 -1
-2 -2
0 5
1 0
-1 -1
-4 3

Xem đáp số

1 0
0 5
-4 3
-1 -1
-2 -2
3 -1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Bóc từng lớp vỏ

Dòng đầu là n (1 ≤ n ≤ 2000), n dòng sau là tọa độ nguyên các điểm khác nhau (|x|, |y| ≤ 10⁶). Mỗi lần, bỏ đi tất cả các điểm nằm trên biên bao lồi của các điểm còn lại (kể cả điểm nằm giữa cạnh; nếu chỉ còn 1, 2 điểm hoặc các điểm thẳng hàng thì bỏ hết). In ra số lần bỏ cho tới khi hết điểm.

Ví dụ:

Nhập	In ra
9 0 0 4 0 4 4 0 4 1 1 3 1 2 3 2 2 2 0	3

Kiểm tra: nhập

12
1 -5
0 -2
6 3
6 0
1 -1
-4 -2
6 4
1 -4
-5 5
4 4
-5 6
-2 4

Xem đáp số

3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Dây bao quanh các giếng tròn

Dòng đầu có n và r (1 ≤ n ≤ 10⁵, 1 ≤ r ≤ 10⁴). n dòng sau là tâm của n cái giếng tròn bán kính r (tọa độ nguyên, |x|, |y| ≤ 10⁶). Căng một sợi dây bao quanh tất cả các giếng. In ra độ dài sợi dây, làm tròn 3 chữ số sau dấu phẩy.

Ví dụ:

Nhập	In ra
4 1 0 0 4 0 4 3 0 3	20.283

Kiểm tra: nhập

10 3
31 -14
30 -5
-20 31
-9 -7
17 -4
-29 41
-7 -5
7 42
8 -49
-3 9

Xem đáp số

255.434

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Xoay compa

Bài 6. Hai điểm xa nhau nhất

Dòng đầu là n (2 ≤ n ≤ 10⁵), n dòng sau là tọa độ nguyên các điểm (|x|, |y| ≤ 10⁹). In ra bình phương khoảng cách lớn nhất giữa hai điểm.

Ví dụ:

Nhập	In ra
4 0 0 3 0 0 4 1 1	25

Kiểm tra: nhập

12
-51 75
45 39
87 -91
-73 19
86 -4
27 -99
-89 -9
17 70
68 52
70 33
-11 70
71 76

Xem đáp số

46600

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Khe hẹp nhất

Dòng đầu là n (3 ≤ n ≤ 10⁵), n dòng sau là tọa độ nguyên các điểm (|x|, |y| ≤ 10⁶, không phải tất cả thẳng hàng). Tìm khoảng cách nhỏ nhất giữa hai đường thẳng song song kẹp tất cả các điểm ở giữa (bề rộng của tập điểm). In ra kết quả làm tròn 3 chữ số sau dấu phẩy.

Ví dụ:

Nhập	In ra
4 0 0 4 0 4 2 0 2	2.000

Kiểm tra: nhập

12
91 -29
27 -74
-72 40
49 -39
36 -43
20 37
36 -90
-27 -55
54 -70
-61 43
-4 -89
-18 10

Xem đáp số

108.626

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Hộp chữ nhật nhỏ nhất

Dòng đầu là n (3 ≤ n ≤ 10⁵), n dòng sau là tọa độ nguyên các điểm (|x|, |y| ≤ 10⁴, không phải tất cả thẳng hàng). Hình chữ nhật (có thể đặt nghiêng) chứa tất cả các điểm có diện tích nhỏ nhất là bao nhiêu? In ra kết quả làm tròn 3 chữ số sau dấu phẩy.

Ví dụ:

Nhập	In ra
4 0 0 2 2 4 0 2 -2	8.000

Kiểm tra: nhập

12
-74 -48
-10 -71
97 26
-76 27
59 -80
-66 -16
34 -47
22 -61
62 76
-24 78
49 -28
-74 94

Xem đáp số

27690.236

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Hộp chữ nhật có chu vi nhỏ nhất

Dòng đầu là n (3 ≤ n ≤ 10⁵), n dòng sau là tọa độ nguyên các điểm (|x|, |y| ≤ 10⁴, không phải tất cả thẳng hàng). Hình chữ nhật (có thể đặt nghiêng) chứa tất cả các điểm có chu vi nhỏ nhất là bao nhiêu? In ra kết quả làm tròn 3 chữ số sau dấu phẩy.

Ví dụ:

Nhập	In ra
4 0 0 2 2 4 0 2 -2	11.314

Kiểm tra: nhập

12
10 68
-25 -71
49 -61
-2 94
24 -32
82 75
-18 93
63 24
-1 73
4 19
67 54
45 77

Xem đáp số

533.015

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Tam giác lớn nhất với nhiều điểm

Dòng đầu là n (3 ≤ n ≤ 5000), n dòng sau là tọa độ nguyên các điểm (|x|, |y| ≤ 10⁸). Chọn 3 điểm tạo tam giác có diện tích lớn nhất. In ra hai lần diện tích đó.

Ví dụ:

Nhập	In ra
5 0 0 4 0 4 4 0 4 2 2	16

Kiểm tra: nhập

12
-85 94
94 -50
-77 42
-4 -59
4 84
-5 44
66 98
2 99
46 -50
55 -88
-93 88
81 91

Xem đáp số

31068

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Đa giác lồi: câu hỏi, cắt, giao, tổng

Bài 11. Nhiều điểm trong đa giác lồi

Dòng đầu là n (3 ≤ n ≤ 10⁵), n dòng sau là các đỉnh của một đa giác lồi theo chiều ngược kim đồng hồ (không có ba đỉnh thẳng hàng, |x|, |y| ≤ 10⁹). Dòng tiếp là Q (Q ≤ 10⁵), Q dòng sau mỗi dòng là một điểm. Với mỗi điểm in ra TRONG, BIEN hoặc NGOAI.

Ví dụ:

Nhập	In ra
4 0 0 4 0 4 4 0 4 4 2 2 4 1 5 5 0 0	TRONG BIEN NGOAI BIEN

Kiểm tra: nhập

7
-9 1
-6 -7
3 -9
9 -2
6 7
3 9
-8 5
6
-6 15
-12 -7
15 -13
-7 3
-1 -10
-9 1

Xem đáp số

NGOAI
NGOAI
NGOAI
TRONG
NGOAI
BIEN

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Cắt đa giác lồi bằng một nhát

Dòng đầu là n (3 ≤ n ≤ 10⁵), n dòng sau là các đỉnh của một đa giác lồi theo chiều ngược kim đồng hồ (tọa độ nguyên, |x|, |y| ≤ 10⁴). Dòng cuối có 4 số nguyên x_A, y_A, x_B, y_B (A khác B). Cắt đa giác bằng đường thẳng AB. In ra diện tích phần nằm bên trái đường thẳng có hướng từ A đến B, làm tròn 3 chữ số sau dấu phẩy.

Ví dụ:

Nhập	In ra
4 0 0 4 0 4 4 0 4 0 1 4 3	8.000

Kiểm tra: nhập

7
-15 12
18 -8
19 -3
19 5
15 13
6 18
-13 14
-19 -16 4 11

Xem đáp số

162.244

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Giao của hai đa giác lồi

Dòng đầu là n, n dòng sau là các đỉnh của đa giác lồi thứ nhất; tiếp theo là m và m đỉnh của đa giác lồi thứ hai (3 ≤ n, m ≤ 1000, cả hai theo chiều ngược kim đồng hồ, tọa độ nguyên |x|, |y| ≤ 10⁴). In ra diện tích phần chung của hai đa giác, làm tròn 3 chữ số sau dấu phẩy.

Ví dụ:

Nhập	In ra
4 0 0 4 0 4 4 0 4 4 2 2 6 2 6 6 2 6	4.000

Kiểm tra: nhập

6
-19 0
4 -19
10 -17
14 13
-1 19
-8 18
6
-13 7
-8 -10
17 -13
25 -1
1 22
-9 15

Xem đáp số

626.750

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 14. Tổng Minkowski

Cho hai đa giác lồi P (n đỉnh) và Q (m đỉnh), mỗi đa giác theo chiều ngược kim đồng hồ, không có ba đỉnh thẳng hàng (3 ≤ n, m ≤ 10⁵, tọa độ nguyên |x|, |y| ≤ 10⁸). Tổng Minkowski P + Q là tập mọi điểm (p_x + q_x, p_y + q_y) với p thuộc P, q thuộc Q. In ra hai lần diện tích của P + Q. Dữ liệu vào: dòng n, n đỉnh, dòng m, m đỉnh.

Ví dụ:

Nhập	In ra
4 0 0 1 0 1 1 0 1 3 0 0 2 0 0 2	14

Kiểm tra: nhập

6
-93 35
-90 -42
-11 -99
96 27
53 84
-88 45
5
-32 -6
29 -13
31 -9
-13 30
-32 5

Xem đáp số

77592

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Vùng an toàn

Một vùng đất hình vuông có |x|, |y| ≤ 10⁵. Có n đường thẳng (1 ≤ n ≤ 2000), mỗi đường cho bởi hai điểm nguyên A, B khác nhau (|x|, |y| ≤ 10⁴); vùng an toàn phải nằm bên trái (hoặc trên) mọi đường thẳng có hướng từ A đến B. Dòng đầu là n, mỗi dòng sau có 4 số x_A, y_A, x_B, y_B. In ra diện tích vùng an toàn (phần của hình vuông thỏa mọi điều kiện), làm tròn 3 chữ số sau dấu phẩy.

Ví dụ:

Nhập	In ra
3 0 0 10 0 10 0 0 10 0 10 0 0	50.000

Kiểm tra: nhập

12
-2136 -7636 -1174 -7905
4728 -4932 5448 -4240
-1797 -1982 -1058 -2653
-1981 2653 -2783 2055
4961 -2809 5452 -1939
3734 3338 3067 4083
-4266 -2085 -3828 -2983
3360 2676 2736 3458
-945 -6402 43 -6548
1627 3656 713 4062
-1951 -752 -1593 -1685
4607 6680 3783 7247

Xem đáp số

54035001.774

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Góc cực và vận dụng

Bài 16. Tam giác chứa gốc tọa độ

Dòng đầu là n (3 ≤ n ≤ 2000), n dòng sau là tọa độ nguyên các điểm (|x|, |y| ≤ 10⁹), không điểm nào trùng gốc O và không có hai điểm nào cùng nằm trên một đường thẳng qua O. In ra số tam giác có ba đỉnh là ba điểm đã cho và chứa O ở bên trong.

Ví dụ:

Nhập	In ra
4 2 1 -1 3 -3 -1 1 -2	2

Kiểm tra: nhập

10
5 11
-1 13
-10 -9
-3 5
13 -2
-14 13
13 -4
19 -2
-9 9
8 -2

Xem đáp số

20

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 17. Khi nào bao được gốc tọa độ

Dòng đầu là n (1 ≤ n ≤ 10⁵), n dòng sau là tọa độ nguyên các điểm theo thứ tự xuất hiện (|x|, |y| ≤ 10⁹). Tìm k nhỏ nhất sao cho bao lồi của k điểm đầu tiên chứa gốc O ở bên trong (không tính trên biên). In ra k, hoặc -1 nếu không có.

Ví dụ:

Nhập	In ra
5 1 1 2 3 -1 1 0 -2 5 5	4

Kiểm tra: nhập

12
6 -3
9 7
9 3
6 5
3 7
7 8
8 1
-8 -9
8 4
7 8
10 4
7 3

Xem đáp số

8

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 18. Điểm nguyên trên biên bao lồi

Dòng đầu là n (3 ≤ n ≤ 10⁵), n dòng sau là tọa độ nguyên các điểm (|x|, |y| ≤ 10⁸, không phải tất cả thẳng hàng). In ra số điểm có tọa độ nguyên nằm trên biên bao lồi của các điểm đã cho.

Ví dụ:

Nhập	In ra
5 0 0 4 0 4 3 0 3 2 1	14

Kiểm tra: nhập

10
-9 8
-4 -12
-3 0
-10 8
5 7
-1 -6
-3 6
-7 -12
-7 -6
-3 1

Xem đáp số

10

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 19. Điểm nguyên bên trong bao lồi

Dòng đầu là n (3 ≤ n ≤ 10⁵), n dòng sau là tọa độ nguyên các điểm (|x|, |y| ≤ 10⁸, không phải tất cả thẳng hàng). In ra số điểm có tọa độ nguyên nằm hẳn bên trong bao lồi của các điểm đã cho.

Ví dụ:

Nhập	In ra
5 0 0 4 0 4 3 0 3 2 1	6

Kiểm tra: nhập

10
4 10
-9 -2
12 8
9 9
2 10
4 -1
8 6
-9 -3
-12 -4
3 -8

Xem đáp số

216

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 20. Bỏ một cây cọc

Dòng đầu là n (4 ≤ n ≤ 1000), n dòng sau là tọa độ nguyên các cây cọc khác nhau (|x|, |y| ≤ 10⁶). Người ta được nhổ đi đúng một cây cọc, rồi căng dây quanh các cọc còn lại. In ra hai lần diện tích nhỏ nhất có thể của vùng bên trong dây (bằng 0 nếu các cọc còn lại thẳng hàng).

Ví dụ:

Nhập	In ra
5 0 0 4 0 4 4 0 4 5 2	20

Kiểm tra: nhập

10
17 -19
3 -17
-15 18
17 -18
16 20
-10 19
-17 -4
9 -11
-16 7
-15 2

Xem đáp số

1164

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.