Diện tích đa giác và điểm nguyên

Mức độ: Nâng cao

Bài Điểm, khoảng cách và tích có hướng cho biết tích có hướng bằng hai lần diện tích tam giác. Bài này mở rộng ra đa giác bất kỳ, rồi dùng diện tích để đếm điểm nguyên mà không cần duyệt từng điểm.

Công thức Shoelace (dây giày)

Đa giác có các đỉnh P₁, P₂, …, P_n theo thứ tự đi quanh. Chia đa giác thành các tam giác chung đỉnh O (gốc tọa độ), cộng diện tích có dấu của các tam giác O P_i P_{i + 1}. Phần nằm ngoài đa giác được cộng rồi trừ đi, tự triệt tiêu:

2S = |x₁y₂ - x₂y₁ + x₂y₃ - x₃y₂ + … + x_ny₁ - x₁y_n|

Mỗi số hạng là tích có hướng OP_i × OP_{i + 1}. Tên “dây giày” đến từ cách nhân chéo các tọa độ khi viết thành hai cột.

Hình chữ nhật (0, 0), (4, 0), (4, 3), (0, 3):

i	x_iy_{i + 1} - x_{i + 1}y_i
1	0 × 0 - 4 × 0 = 0
2	4 × 3 - 4 × 0 = 12
3	4 × 3 - 0 × 3 = 12
4	0 × 0 - 0 × 3 = 0

2S = 24, S = 12. Đúng là 4 × 3.

Python
C++

n = int(input())
p = [tuple(map(int, input().split())) for _ in range(n)]
hai_s = 0
for i in range(n):
    x1, y1 = p[i]
    x2, y2 = p[(i + 1) % n]          # đỉnh cuối nối về đỉnh đầu
    hai_s += x1 * y2 - x2 * y1
print(abs(hai_s) / 2)

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

int main() {
    int n;
    cin >> n;
    vector<long long> x(n), y(n);
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
    long long haiS = 0;
    for (int i = 0; i < n; i++) {
        int j = (i + 1) % n;                     // đỉnh cuối nối về đỉnh đầu
        haiS += x[i] * y[j] - x[j] * y[i];
    }
    cout << llabs(haiS) / 2.0 << endl;
    return 0;
}

Dấu của 2S (trước khi lấy trị tuyệt đối) cho biết chiều đi: dương là ngược chiều kim đồng hồ, âm là cùng chiều. Công thức chỉ đúng khi các cạnh không tự cắt nhau.

Điểm nguyên trên cạnh

Đoạn thẳng từ (x₁, y₁) đến (x₂, y₂) có ƯCLN(|dx|, |dy|) + 1 điểm nguyên (bài điểm nguyên trên đoạn thẳng). Cộng cho cả đa giác (mỗi đỉnh chỉ tính một lần): B = tổng ƯCLN(|dx|, |dy|) của các cạnh.

Định lý Pick

Với đa giác có đỉnh là điểm nguyên (và không tự cắt), gọi I là số điểm nguyên bên trong, B là số điểm nguyên trên biên:

S = I + B / 2 - 1

Kiểm tra với hình vuông 2 × 2 đỉnh (0, 0): S = 4, B = 8 (4 đỉnh và 4 trung điểm cạnh), I = 1 (điểm (1, 1)): 1 + 4 - 1 = 4. Đúng.

Biết S (từ Shoelace) và B (từ ƯCLN), suy ra ngay I = S - B / 2 + 1, đếm được điểm nguyên bên trong đa giác có tọa độ tới 10⁹ mà không cần duyệt.

Bao lồi

Bao lồi của một tập điểm là đa giác lồi nhỏ nhất chứa mọi điểm, như sợi dây chun căng bao quanh các cái đinh. Thuật toán chuỗi đơn điệu (monotone chain):

Sắp xếp các điểm theo x, rồi theo y.
Dựng nửa dưới: đi từ trái sang phải, thêm từng điểm; trong khi hai điểm cuối của nửa dưới cùng điểm mới không rẽ trái (tích có hướng ≤ 0) thì bỏ điểm cuối.
Dựng nửa trên tương tự, đi từ phải sang trái.
Ghép hai nửa (bỏ điểm trùng ở hai đầu).

Sắp xếp tốn n log n, phần còn lại mỗi điểm được thêm và bỏ nhiều nhất một lần (bài 14).

Luyện tập

Gồm 20 bài, chia thành 3 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. Diện tích đa giác

Bài 1. Diện tích đa giác

Dòng đầu là n (3 ≤ n ≤ 10⁵). n dòng tiếp theo là tọa độ nguyên các đỉnh theo thứ tự đi quanh (giá trị tuyệt đối ≤ 10⁶, đa giác không tự cắt). In ra diện tích, đúng một chữ số sau dấu chấm.

Ví dụ:

Nhập	In ra
`4` `0 0` `4 0` `4 3` `0 3`	`12.0`

Kiểm tra: nhập

Xem đáp số

22.5

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

Bài 2. Chiều đi quanh đa giác

Dòng đầu là n, n dòng tiếp theo là các đỉnh của đa giác không tự cắt theo thứ tự cho trước. In ra NGUOC nếu thứ tự đi ngược chiều kim đồng hồ, XUOI nếu cùng chiều.

Ví dụ:

Nhập	In ra
`3` `0 0` `4 0` `0 3`	`NGUOC`

Kiểm tra: nhập

Xem đáp số

XUOI

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

Bài 3. Mảnh đất nào rộng hơn

Hai mảnh đất hình đa giác, mỗi mảnh cho bởi: một dòng n, rồi n dòng tọa độ đỉnh. In ra 1, 2 hoặc BANG cho biết mảnh nào có diện tích lớn hơn.

Ví dụ:

Nhập	In ra
`4` `0 0` `2 0` `2 2` `0 2` `3` `0 0` `4 0` `0 2`	`BANG`

Kiểm tra: nhập

Xem đáp số

1

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

Bài 4. Diện tích hình chữ L

Một hình chữ L có các cạnh song song trục, cho bởi 6 đỉnh theo thứ tự đi quanh (dòng đầu là 6, sau đó 6 dòng tọa độ). In ra diện tích (số nguyên).

Ví dụ:

Nhập	In ra
`6` `0 0` `4 0` `4 1` `1 1` `1 3` `0 3`	`6`

Kiểm tra: nhập

Xem đáp số

55

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

Bài 5. Đường chéo chia đa giác lồi

Dòng đầu có n, a, b (3 ≤ n ≤ 10⁵, 1 ≤ a nhỏ hơn b ≤ n, a và b không kề nhau). n dòng tiếp theo là các đỉnh của một đa giác lồi. Đường chéo nối đỉnh a và đỉnh b chia đa giác thành hai phần. In ra 2 lần diện tích phần nhỏ hơn và 2 lần diện tích phần lớn hơn.

Ví dụ:

Nhập	In ra
`4 1 3` `0 0` `4 0` `4 4` `0 4`	`16 16`

Kiểm tra: nhập

Xem đáp số

18 78

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

Bài 6. Diện tích hợp hai hình chữ nhật

Mỗi dòng trong hai dòng là một hình chữ nhật cạnh song song trục: x1 y1 x2 y2 (góc dưới trái, góc trên phải, giá trị tuyệt đối ≤ 10⁹). In ra diện tích phần mặt phẳng bị ít nhất một hình chữ nhật phủ.

Ví dụ:

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

Kiểm tra: nhập

-5 -5 5 5
0 -10 3 2

Xem đáp số

115

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

Bài 7. Tổng diện tích nhiều hình chữ nhật

Dòng đầu là k (k ≤ 10⁴). k dòng tiếp theo, mỗi dòng là một hình chữ nhật x1 y1 x2 y2 với 0 ≤ x1 nhỏ hơn x2 ≤ 1000 và 0 ≤ y1 nhỏ hơn y2 ≤ 1000. In ra diện tích phần bị ít nhất một hình phủ.

Ví dụ:

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

Kiểm tra: nhập

Xem đáp số

53

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

Nhóm 2. Điểm nguyên

Bài 8. Điểm nguyên trên biên

Dòng đầu là n, n dòng tiếp theo là các đỉnh nguyên của đa giác theo thứ tự (giá trị tuyệt đối ≤ 10⁹). In ra số điểm nguyên nằm trên biên đa giác.

Ví dụ:

Nhập	In ra
`3` `0 0` `4 0` `0 4`	`12`

Kiểm tra: nhập

Xem đáp số

8

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

Bài 9. Điểm nguyên bên trong (định lý Pick)

Dòng đầu là n, n dòng tiếp theo là các đỉnh nguyên của đa giác không tự cắt (giá trị tuyệt đối ≤ 10⁹). In ra số điểm nguyên nằm hẳn bên trong đa giác.

Ví dụ:

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

Kiểm tra: nhập

Xem đáp số

40

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

Bài 10. Điểm nguyên trong hình tròn

Nhập r (r ≤ 10⁶). Đếm các điểm nguyên (x, y) với x² + y² ≤ r² (trong hoặc trên đường tròn tâm O bán kính r).

Ví dụ: nhập 2 thì in ra 13.

Kiểm tra: nhập 10.

Xem đáp số

317

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

Bài 11. Điểm nguyên trên đường tròn

Nhập r (1 ≤ r ≤ 10⁶). Đếm các điểm nguyên (x, y) nằm đúng trên đường tròn x² + y² = r².

Ví dụ: nhập 5 thì in ra 12.

Kiểm tra: nhập 25.

Xem đáp số

20

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

Bài 12. Đường chéo cắt qua bao nhiêu ô

Hình chữ nhật m × n ô vuông (m, n ≤ 10¹⁸). Kẻ đường chéo từ góc này sang góc đối diện. Đường chéo đi qua phần bên trong của bao nhiêu ô?

Ví dụ: nhập 2 3 thì in ra 4.

Kiểm tra: nhập 6 4.

Xem đáp số

8

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

Bài 13. Số ô bên trong tam giác vuông

Tam giác vuông có đỉnh (0, 0), (a, 0), (0, b) với a, b nguyên dương (≤ 10⁹). Đếm các điểm nguyên nằm hẳn bên trong tam giác.

Ví dụ: nhập 4 4 thì in ra 3.

Kiểm tra: nhập 12 8.

Xem đáp số

37

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

Nhóm 3. Bao lồi và vận dụng

Bài 14. Số đỉnh của bao lồi

Dòng đầu là n (n ≤ 10⁵). n dòng tiếp theo là tọa độ nguyên các điểm (có thể trùng nhau). In ra số đỉnh của bao lồi (không tính các điểm nằm giữa một cạnh).

Ví dụ:

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

Kiểm tra: nhập

Xem đáp số

7

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

Bài 15. Diện tích bao lồi

Dòng đầu là n (3 ≤ n ≤ 10⁵). n dòng tiếp theo là tọa độ nguyên các điểm (không phải tất cả thẳng hàng). In ra hai lần diện tích bao lồi.

Ví dụ:

Nhập	In ra
`5` `0 0` `4 0` `4 4` `0 4` `2 2`	`32`

Kiểm tra: nhập

Xem đáp số

72

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

Bài 16. Chu vi hàng rào

Dòng đầu là n (3 ≤ n ≤ 10⁵). n dòng tiếp theo là tọa độ nguyên các cây. Cần rào một hàng rào ngắn nhất bao quanh mọi cây. In ra độ dài hàng rào, làm tròn đến 2 chữ số sau dấu chấm.

Ví dụ:

Nhập	In ra
`4` `0 0` `3 0` `3 4` `1 1`	`12.00`

Kiểm tra: nhập

Xem đáp số

24.00

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

Bài 17. Điểm trong đa giác lồi

Dòng đầu là n, n dòng tiếp theo là các đỉnh của một đa giác lồi theo thứ tự ngược chiều kim đồng hồ. Dòng cuối là điểm P. In ra TRONG, TREN CANH hoặc NGOAI.

Ví dụ:

Nhập	In ra
`4` `0 0` `4 0` `4 4` `0 4` `2 2`	`TRONG`

Kiểm tra: nhập

Xem đáp số

NGOAI

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

Bài 18. Điểm trong đa giác bất kỳ

Dòng đầu là n, n dòng tiếp theo là các đỉnh nguyên của đa giác không tự cắt (có thể lõm). Dòng cuối là điểm nguyên P không nằm trên biên. In ra TRONG hoặc NGOAI.

Ví dụ:

Nhập	In ra
`4` `0 0` `4 0` `4 4` `0 4` `2 2`	`TRONG`

Kiểm tra: nhập

Xem đáp số

NGOAI

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

Bài 19. Tam giác lớn nhất

Dòng đầu là n (3 ≤ n ≤ 200). n dòng tiếp theo là tọa độ nguyên các điểm. 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
`4` `0 0` `4 0` `0 3` `1 1`	`12`

Kiểm tra: nhập

Xem đáp số

44

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

Bài 20. Đếm điểm nguyên trong tam giác bất kỳ

Nhập tọa độ nguyên ba đỉnh tam giác (giá trị tuyệt đối ≤ 10⁹, không thẳng hàng). In ra số điểm nguyên nằm trong hoặc trên cạnh tam giác.

Ví dụ:

Nhập	In ra
`0 0` `4 0` `0 4`	`15`

Kiểm tra: nhập

-3 -2
7 1
2 9

Xem đáp số

50

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

Th.S Trần Huy Phúc

Kỹ sư phần mềm @Adnovum & Bumbii Academy

Học Tiếng Anh với Bumbii English