Chuyên đề nâng cao 1: Hình học tính toán cơ bản trong C++ và Python: tích có hướng, giao hai đoạn thẳng, diện tích đa giác, bao lồi

Series: Chuyên đề nâng cao Độ khó: Khá Chuyên đề nâng cao 1 / Thuật toán nâng cao Hình học Bao lồi

// Chuyên đề nâng cao · Chuyên đề 1

Hình học tính toán cơ bản: tích có hướng, giao đoạn thẳng, diện tích đa giác, bao lồi

Chỉ với một công thức nhân trừ hai số, em biết được điểm nằm bên trái hay bên phải, hai đoạn có cắt nhau không, diện tích đa giác bao nhiêu, và dựng được hàng rào ngắn nhất bao quanh mọi điểm. Không cần một con số thực nào.

Lời mở đầu

Đề HSG cấp tỉnh và thi chuyên Tin thỉnh thoảng có một câu hình học: kiểm tra điểm nằm trong tam giác, hai con đường có giao nhau không, tính diện tích mảnh đất có toạ độ các góc, dựng hàng rào bao quanh các cây… Nhiều bạn sợ dạng này vì nghĩ phải dùng góc, sin, cos, phương trình đường thẳng, rồi loay hoay với sai số. Thực ra gần như tất cả các bài cơ bản đều giải được bằng một công cụ duy nhất: tích có hướng của hai vector, tính hoàn toàn bằng số nguyên.

Em đã gặp tích có hướng ở Chuyên đề 2: Số thực (tính diện tích tam giác mà không cần số thực). Hôm nay ta khai thác hết sức mạnh của nó. Bài cần struct và sắp xếp theo nhiều khoá ở bài 10, hàm gcd ở bài 12, và kỹ thuật ngăn xếp giữ “đường biên đẹp” rất giống bài 25: Ngăn xếp đơn điệu. Bài tập cặp điểm gần nhất ở bài 24 cũng là một bài hình học, lần này ta làm bài “ngược lại”: cặp điểm xa nhất.

Chuyên đề 1Hình học tính toánChuyên đề 2Lũy thừa ma trận

Trong bài này bạn sẽ học: biểu diễn điểm, vector bằng long long; tích vô hướng và tích có hướng cùng ý nghĩa hình học của chúng; xác định hướng rẽ của ba điểm và kiểm tra điểm nằm trên đoạn; kiểm tra hai đoạn thẳng cắt nhau, kể cả khi chúng thẳng hàng và chồng lên nhau; tính diện tích đa giác bằng công thức Shoelace, xác định điểm trong đa giác bằng tia, đếm điểm nguyên bằng định lý Pick; dựng bao lồi bằng thuật toán Andrew và tính chu vi, diện tích của nó. Có 2 khung chạy tay, 3 mô phỏng bấm từng bước và 8 bài tập kèm gợi ý.

Lộ trình bài viết, bấm vào từng phần để nhảy tới:

Phần 1Điểm, vector, tích có hướngPhần 2Hướng của 3 điểmPhần 3Giao hai đoạn thẳngPhần 4Đa giác: diện tích, PickPhần 5Bao lồi AndrewBài tập8 bài + gợi ý

Phần 1Điểm, vector, tích vô hướng và tích có hướng

Trong lập trình, một điểm chỉ là cặp số $(x, y)$. Một vector cũng là cặp số $(x, y)$, nhưng hiểu là “một bước dịch chuyển”: sang phải $x$, lên trên $y$. Vector đi từ $A$ tới $B$ là $\vec{AB} = B - A = (x_B - x_A,\ y_B - y_A)$. Vì cùng một dạng nên ta dùng chung một struct cho cả hai:

Khuôn mẫu: điểm và vector

struct P{ long long x, y; };
P operator-(P a, P b){ return {a.x - b.x, a.y - b.y}; }     // vector AB = B - A
long long dot(P a, P b){ return a.x * b.x + a.y * b.y; }     // tích vô hướng
long long cross(P a, P b){ return a.x * b.y - a.y * b.x; }   // tích có hướng
long long cross(P o, P a, P b){ return cross(a - o, b - o); } // dùng nhiều nhất

Trong Python, điểm là một tuple (x, y), và hàm hay dùng nhất là cross(o, a, b) = (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0]).

Với hai vector $\vec a = (a_x, a_y)$ và $\vec b = (b_x, b_y)$ có hai phép “nhân” quan trọng:

• Tích vô hướng $\vec a \cdot \vec b = a_x b_x + a_y b_y = |\vec a|\,|\vec b| \cos\theta$. Dấu của nó cho biết góc giữa hai vector: dương là góc nhọn, bằng 0 là góc vuông, âm là góc tù.
• Tích có hướng $\vec a \times \vec b = a_x b_y - a_y b_x = |\vec a|\,|\vec b| \sin\theta$, với $\theta$ là góc quay ngược chiều kim đồng hồ từ $\vec a$ sang $\vec b$. Giá trị tuyệt đối của nó là diện tích hình bình hành dựng trên hai vector; dấu của nó cho biết $\vec b$ nằm bên trái (dương) hay bên phải (âm) của $\vec a$, bằng 0 khi hai vector cùng phương.

Hình 1. $\vec a = (4, 1)$, $\vec b = (1, 3)$. Tích có hướng bằng 11 là diện tích hình bình hành tô xanh, nên tam giác tạo bởi hai vector có diện tích 5,5. Dấu dương: $\vec b$ nằm bên trái $\vec a$.

Cách nhớ dấu: đặt tay phải sao cho các ngón tay quay từ $\vec a$ sang $\vec b$ theo góc nhỏ hơn 180°. Nếu chiều quay ngược kim đồng hồ (giống chiều tăng của góc trong lượng giác) thì tích có hướng dương. Đổi thứ tự hai vector là đổi dấu: $\vec b \times \vec a = -(\vec a \times \vec b)$. Em tự thay đổi ba điểm trong mô phỏng dưới đây để cảm nhận dấu và độ lớn:

MÔ PHỎNGTích có hướng: B nằm bên trái hay bên phải tia OA?Nhập toạ độ ba điểm O, A, B (mỗi số từ -6 đến 6) rồi bấm Tiếp. Hình bình hành tô màu có diện tích đúng bằng |a × b|.

O (x y)A (x y)B (x y)

ChậmVừaNhanh

vector a = OAvector b = OBa × b > 0 (B bên trái)a × b < 0 (B bên phải)

Xem code C++ / Python: tích vô hướng, tích có hướng và diện tích tam giác (bấm để mở)

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

struct P{
    long long x, y;
};
P operator-(P a, P b){ return {a.x - b.x, a.y - b.y}; }      // vector AB = B - A
long long dot(P a, P b){ return a.x * b.x + a.y * b.y; }      // tích vô hướng
long long cross(P a, P b){ return a.x * b.y - a.y * b.x; }    // tích có hướng

int main(){
    P O, A, B;
    cin >> O.x >> O.y >> A.x >> A.y >> B.x >> B.y;
    P a = A - O, b = B - O;
    long long d = dot(a, b), c = cross(a, b);
    cout << d << " " << c << "\n";
    if(d > 0) cout << "goc nhon\n";
    else if(d == 0) cout << "goc vuong\n";
    else cout << "goc tu\n";
    long long s2 = llabs(c);                                   // 2 lần diện tích tam giác OAB
    cout << s2 / 2 << (s2 % 2 ? ".5" : ".0");
    return 0;
}

def dot(a, b):                          # tích vô hướng
    return a[0] * b[0] + a[1] * b[1]

def cross(a, b):                        # tích có hướng
    return a[0] * b[1] - a[1] * b[0]

ox, oy, ax, ay, bx, by = map(int, input().split())
a = (ax - ox, ay - oy)                  # vector OA
b = (bx - ox, by - oy)                  # vector OB
d, c = dot(a, b), cross(a, b)
print(d, c)
print('goc nhon' if d > 0 else ('goc vuong' if d == 0 else 'goc tu'))
s2 = abs(c)                             # 2 lần diện tích tam giác OAB
print(s2 // 2, '.5' if s2 % 2 else '.0', sep='')

Vì sao luôn cố dùng số nguyên?

Toạ độ nguyên thì tích vô hướng, tích có hướng, diện tích nhân đôi đều là số nguyên chính xác tuyệt đối. Kết luận “dương, âm hay bằng 0” không bao giờ sai. Nếu chuyển sang double, một giá trị đúng ra bằng 0 có thể thành $10^{-16}$ và chương trình kết luận “rẽ trái” cho ba điểm thẳng hàng. Chỉ dùng số thực khi đề bắt in ra độ dài (cần căn bậc hai), góc (atan2) hay toạ độ giao điểm (cần phép chia), và khi đó nhớ các mẹo so sánh với sai số eps ở Chuyên đề 2. Mọi phép so sánh, kiểm tra vẫn nên làm bằng số nguyên.

Tràn số

Toạ độ tới $10^9$ thì hiệu toạ độ tới $2 \cdot 10^9$, tích có hướng tới $2 \cdot (2 \cdot 10^9)^2 = 8 \cdot 10^{18}$, vẫn vừa long long (giới hạn khoảng $9{,}2 \cdot 10^{18}$), nhưng không còn chỗ cho thêm phép nhân nào. Vì vậy khi so sánh dấu của hai tích có hướng, đừng viết cross1 * cross2 < 0 (tràn!), hãy lấy dấu từng cái trước. Khi đề cho toạ độ nhỏ (đến $10^6$) thì thoải mái hơn. Python không bao giờ tràn số nguyên, nhưng nhớ dùng // thay vì /.

Phần 2Hướng của ba điểm và điểm nằm trên đoạn

Cho ba điểm $A, B, C$. Đi từ $A$ tới $B$ rồi rẽ sang $C$: rẽ trái, rẽ phải hay đi thẳng? Chỉ cần tính $\text{cross}(A, B, C) = \vec{AB} \times \vec{AC}$:

• $> 0$: $C$ nằm bên trái đường thẳng $AB$ (đi $A \to B \to C$ là rẽ trái, ba điểm theo thứ tự ngược chiều kim đồng hồ);
• $< 0$: $C$ nằm bên phải (rẽ phải, cùng chiều kim đồng hồ);
• $= 0$: ba điểm thẳng hàng.

Hình 2. Ba khả năng của bộ ba điểm. Hàm cross(A, B, C) là “la bàn” của mọi thuật toán trong bài này.

A	B	C	$\vec{AB}$	$\vec{AC}$	cross(A, B, C)	Kết luận
(0, 1)	(3, 2)	(1, 4)	(3, 1)	(1, 3)	3·3 − 1·1 = 8	rẽ trái
(0, 1)	(3, 2)	(4, 0)	(3, 1)	(4, −1)	3·(−1) − 1·4 = −7	rẽ phải
(0, 0)	(2, 1)	(4, 2)	(2, 1)	(4, 2)	2·2 − 1·4 = 0	thẳng hàng
(0, 0)	(2, 1)	(6, 3)	(2, 1)	(6, 3)	2·3 − 1·6 = 0	thẳng hàng, C ngoài đoạn AB

Bảng 1. Tính hướng rẽ cho các bộ ba điểm của Hình 2 và một bộ thẳng hàng nhưng C nằm ngoài đoạn.

Điểm $C$ nằm trên đoạn $AB$ khi và chỉ khi hai điều kiện cùng đúng: $C$ thẳng hàng với $A, B$ (tích có hướng bằng 0), và $C$ nằm giữa $A$, $B$. Khi đã thẳng hàng, “nằm giữa” chỉ cần kiểm tra $C$ nằm trong hình chữ nhật bao của đoạn: $\min(x_A, x_B) \le x_C \le \max(x_A, x_B)$ và tương tự với $y$. Dòng cuối của Bảng 1 là ví dụ “thẳng hàng nhưng nằm ngoài”: $C = (6, 3)$ nằm trên đường thẳng $AB$ kéo dài chứ không nằm trên đoạn.

Xem code C++ / Python: hướng của ba điểm và điểm nằm trên đoạn (bấm để mở)

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

struct P{ long long x, y; };

long long cross(P o, P a, P b){            // (a - o) x (b - o)
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
bool onSeg(P a, P b, P c){                 // c nằm trên đoạn AB?
    if(cross(a, b, c) != 0) return false;  // phải thẳng hàng trước đã
    return min(a.x, b.x) <= c.x && c.x <= max(a.x, b.x)
        && min(a.y, b.y) <= c.y && c.y <= max(a.y, b.y);
}

int main(){
    P a, b, c;
    cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y;
    long long v = cross(a, b, c);
    if(v > 0) cout << "TRAI\n";
    else if(v < 0) cout << "PHAI\n";
    else cout << "THANG HANG\n";
    cout << (onSeg(a, b, c) ? "YES" : "NO");
    return 0;
}

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

def on_seg(a, b, c):                    # c nằm trên đoạn AB?
    if cross(a, b, c) != 0:             # phải thẳng hàng trước đã
        return False
    return min(a[0], b[0]) <= c[0] <= max(a[0], b[0]) and min(a[1], b[1]) <= c[1] <= max(a[1], b[1])

v = list(map(int, input().split()))
a, b, c = (v[0], v[1]), (v[2], v[3]), (v[4], v[5])
t = cross(a, b, c)
print('TRAI' if t > 0 else ('PHAI' if t < 0 else 'THANG HANG'))
print('YES' if on_seg(a, b, c) else 'NO')

Một hàm cross(O, A, B) giải được rất nhiều câu hỏi

Điểm trong tam giác $ABC$: tính cross(A, B, P), cross(B, C, P), cross(C, A, P); $P$ nằm trong (hoặc trên biên) khi ba số này không có cặp nào trái dấu (bài tập 2). Đa giác lồi: mọi bộ ba đỉnh liên tiếp phải rẽ cùng một phía (bài tập 6). Diện tích tam giác là |cross(A, B, C)| / 2. Ba điểm thẳng hàng: cross = 0, thay cho việc so sánh hệ số góc bằng phép chia (dễ chia cho 0 và sai số).

Phần 3Giao của hai đoạn thẳng

Bài toán: cho đoạn $AB$ và đoạn $CD$, hai đoạn có điểm chung không? Đây là bài kinh điển và cũng là bài có nhiều bẫy nhất của chương này. Ý tưởng:

• Hai đoạn cắt nhau “kiểu chữ X” khi $C$ và $D$ nằm ở hai phía khác nhau của đường thẳng $AB$, đồng thời $A$ và $B$ nằm ở hai phía khác nhau của đường thẳng $CD$. Tức là $d_1 = \text{cross}(A, B, C)$ và $d_2 = \text{cross}(A, B, D)$ trái dấu, $d_3 = \text{cross}(C, D, A)$ và $d_4 = \text{cross}(C, D, B)$ trái dấu.
• Nếu có một $d_i = 0$ thì một đầu mút nằm trên đường thẳng chứa đoạn kia. Khi đó hai đoạn có điểm chung nếu đầu mút ấy nằm trên đoạn kia (dùng kiểm tra hình chữ nhật bao ở phần 2).

Chỉ một điều kiện “hai phía” là chưa đủ: $C, D$ có thể nằm hai phía của đường thẳng $AB$ nhưng cả đoạn $CD$ lại nằm xa hẳn bên ngoài đoạn $AB$. Vì vậy phải kiểm tra cả hai chiều.

Hình 3. Ba trường hợp có điểm chung và một trường hợp không. Trường hợp 3 và 4 đều có $d_1 = d_2 = d_3 = d_4 = 0$: chỉ phép kiểm tra “nằm trên đoạn” mới phân biệt được.

Em chạy tay chương trình dưới đây với các bộ dữ liệu mẫu khác nhau, đặc biệt là hai bộ thẳng hàng, để thấy vì sao cần đủ bốn dòng kiểm tra cuối:

C++▶ Chạy tay từng dòng codeTính dấu bốn tích có hướng d1, d2, d3, d4 (ô xanh: dương, ô đỏ: âm, ô vàng: bằng 0), rồi xét trường hợp cắt thường và bốn trường hợp chạm.

Dữ liệu vào (stdin) – sửa thoải mái0 0 4 4 0 4 4 0

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4struct P{ long long x, y; };

5

6long long cross(P o, P a, P b){

7 return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);

8}

9int sgn(long long v){ return (v > 0) - (v < 0); }

10bool inBox(P a, P b, P c){

11 return min(a.x, b.x) <= c.x && c.x <= max(a.x, b.x)

12 && min(a.y, b.y) <= c.y && c.y <= max(a.y, b.y);

13}

14

15int main(){

16 P a, b, c, d;

17 cin >> a.x >> a.y >> b.x >> b.y;

18 cin >> c.x >> c.y >> d.x >> d.y;

19 int d1 = sgn(cross(a, b, c)), d2 = sgn(cross(a, b, d));

20 int d3 = sgn(cross(c, d, a)), d4 = sgn(cross(c, d, b));

21 bool ok = false;

22 if(d1 * d2 < 0 && d3 * d4 < 0) ok = true;

23 if(d1 == 0 && inBox(a, b, c)) ok = true;

24 if(d2 == 0 && inBox(a, b, d)) ok = true;

25 if(d3 == 0 && inBox(c, d, a)) ok = true;

26 if(d4 == 0 && inBox(c, d, b)) ok = true;

27 cout << (ok ? "YES" : "NO");

28 return 0;

29}

ChậmVừaNhanhRất nhanh

Xem code C++ / Python: kiểm tra hai đoạn thẳng cắt nhau, nhiều truy vấn (bấm để mở)

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

struct P{ long long x, y; };

long long cross(P o, P a, P b){
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
int sgn(long long v){ return (v > 0) - (v < 0); }
bool inBox(P a, P b, P c){                 // c (đã thẳng hàng) nằm giữa a và b
    return min(a.x, b.x) <= c.x && c.x <= max(a.x, b.x)
        && min(a.y, b.y) <= c.y && c.y <= max(a.y, b.y);
}
bool intersect(P a, P b, P c, P d){
    int d1 = sgn(cross(a, b, c)), d2 = sgn(cross(a, b, d));
    int d3 = sgn(cross(c, d, a)), d4 = sgn(cross(c, d, b));
    if(d1 * d2 < 0 && d3 * d4 < 0) return true;   // cắt nhau "thật sự"
    if(d1 == 0 && inBox(a, b, c)) return true;    // các trường hợp chạm, chồng
    if(d2 == 0 && inBox(a, b, d)) return true;
    if(d3 == 0 && inBox(c, d, a)) return true;
    if(d4 == 0 && inBox(c, d, b)) return true;
    return false;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int q;
    cin >> q;
    while(q--){
        P a, b, c, d;
        cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y;
        cout << (intersect(a, b, c, d) ? "YES" : "NO") << "\n";
    }
    return 0;
}

import sys

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

def sgn(v):
    return (v > 0) - (v < 0)

def in_box(a, b, c):                    # c (đã thẳng hàng) nằm giữa a và b
    return min(a[0], b[0]) <= c[0] <= max(a[0], b[0]) and min(a[1], b[1]) <= c[1] <= max(a[1], b[1])

def intersect(a, b, c, d):
    d1, d2 = sgn(cross(a, b, c)), sgn(cross(a, b, d))
    d3, d4 = sgn(cross(c, d, a)), sgn(cross(c, d, b))
    if d1 * d2 < 0 and d3 * d4 < 0:      # cắt nhau "thật sự"
        return True
    return ((d1 == 0 and in_box(a, b, c)) or (d2 == 0 and in_box(a, b, d)) or
            (d3 == 0 and in_box(c, d, a)) or (d4 == 0 and in_box(c, d, b)))

data = sys.stdin.buffer.read().split()
q = int(data[0])
out = []
for i in range(q):
    v = list(map(int, data[1 + 8 * i: 9 + 8 * i]))
    a, b, c, d = (v[0], v[1]), (v[2], v[3]), (v[4], v[5]), (v[6], v[7])
    out.append('YES' if intersect(a, b, c, d) else 'NO')
print('\n'.join(out))

Ba bẫy hay gặp

1. Nhân hai tích có hướng d1 * d2 khi toạ độ tới $10^9$ sẽ tràn long long: lấy dấu (sgn) trước rồi mới nhân. 2. Quên trường hợp thẳng hàng: hai đoạn nằm trên cùng một đường thẳng, có thể chồng lên nhau hoặc rời nhau, mọi $d_i$ đều bằng 0. 3. Đoạn suy biến thành một điểm ($A = B$): code trên vẫn đúng vì kiểm tra hình chữ nhật bao xử lý luôn trường hợp này.

Còn toạ độ giao điểm thì sao? Khi hai đoạn cắt nhau thường, giao điểm là $A + t \cdot \vec{AB}$ với $t = \dfrac{\text{cross}(C, D, A)}{\text{cross}(C, D, A) - \text{cross}(C, D, B)}$. Đây là lúc bắt buộc dùng số thực (hoặc giữ dạng phân số tử/mẫu nguyên). Nhưng kiểm tra có cắt hay không thì luôn làm bằng số nguyên như trên.

Phần 4Đa giác: diện tích Shoelace, điểm trong đa giác, định lý Pick

Một đa giác cho bởi danh sách đỉnh $P_0, P_1, \ldots, P_{n-1}$ theo thứ tự đi vòng quanh biên (cạnh cuối nối $P_{n-1}$ về $P_0$). Diện tích của nó tính bằng công thức Shoelace (công thức “dây giày”, hay công thức Gauss):

$2S = \left|\displaystyle\sum_{i=0}^{n-1} \left(x_i\, y_{i+1} - x_{i+1}\, y_i\right)\right|$,   với $P_n = P_0$.

Mỗi số hạng $x_i y_{i+1} - x_{i+1} y_i$ chính là $\text{cross}(O, P_i, P_{i+1})$: hai lần diện tích có dấu của tam giác nối gốc toạ độ $O$ với cạnh $P_iP_{i+1}$. Cạnh nào “quay ngược chiều kim đồng hồ” quanh $O$ thì cộng, cạnh nào quay cùng chiều thì trừ. Phần tam giác nằm ngoài đa giác bị cộng rồi lại bị trừ nên triệt tiêu, chỉ còn lại đúng phần bên trong. Công thức đúng cho mọi đa giác đơn (không tự cắt), lồi hay lõm đều được. Bảng dưới tính cho ngũ giác $P_0 \ldots P_4$ = (1, 1), (6, 0), (7, 4), (3, 6), (0, 3):

Cạnh	Từ → tới	$x_i y_{i+1} - x_{i+1} y_i$	Cộng dồn	Điểm nguyên trên cạnh
P0 → P1	(1, 1) → (6, 0)	1·0 − 6·1 = -6	-6	gcd(5, 1) = 1
P1 → P2	(6, 0) → (7, 4)	6·4 − 7·0 = 24	18	gcd(1, 4) = 1
P2 → P3	(7, 4) → (3, 6)	7·6 − 3·4 = 30	48	gcd(4, 2) = 2
P3 → P4	(3, 6) → (0, 3)	3·3 − 0·6 = 9	57	gcd(3, 3) = 3
P4 → P0	(0, 3) → (1, 1)	0·1 − 1·3 = -3	54	gcd(1, 2) = 1
		Tổng	54	B = 8

Bảng 2. Shoelace cho ngũ giác: $2S = 54$, vậy $S = 27$. Tổng dương nên các đỉnh được cho theo chiều ngược kim đồng hồ. Cột cuối dùng cho định lý Pick ở dưới.

Bấm từng bước để thấy “phần thừa” bị trừ ra như thế nào. Em thử cả một đa giác lõm, và thử nhập các đỉnh theo chiều ngược lại xem dấu của tổng đổi ra sao:

MÔ PHỎNGCông thức Shoelace: cộng diện tích có dấu của từng tam giácNhập các đỉnh đa giác theo thứ tự đi vòng (3 đến 8 đỉnh). Xem phần thừa ngoài đa giác bị trừ đi như thế nào.

Các đỉnh (x y, …)

ChậmVừaNhanh

tam giác có số hạng dương (cộng)tam giác có số hạng âm (trừ)cạnh đang xét

Xem code C++ / Python: diện tích đa giác bằng công thức shoelace (bấm để mở)

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

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    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 s2 = 0;                                   // 2 lần diện tích có dấu
    for(int i = 0; i < n; i++){
        int j = (i + 1) % n;                            // đỉnh kế tiếp, vòng về 0
        s2 += x[i] * y[j] - x[j] * y[i];
    }
    s2 = llabs(s2);
    cout << s2 / 2 << (s2 % 2 ? ".5" : ".0");
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
x = [int(v) for v in data[1:2 * n + 1:2]]
y = [int(v) for v in data[2:2 * n + 2:2]]
s2 = 0                                  # 2 lần diện tích có dấu
for i in range(n):
    j = (i + 1) % n                     # đỉnh kế tiếp, vòng về 0
    s2 += x[i] * y[j] - x[j] * y[i]
s2 = abs(s2)
print(s2 // 2, '.5' if s2 % 2 else '.0', sep='')

Diện tích có dấu là thông tin quý

Đừng vội lấy trị tuyệt đối: dấu của tổng cho biết thứ tự đỉnh. Dương là ngược chiều kim đồng hồ, âm là cùng chiều. Nhiều thuật toán yêu cầu đa giác ngược chiều kim đồng hồ, nếu tổng âm em chỉ cần đảo ngược danh sách đỉnh. Ngoài ra $2S$ luôn là số nguyên, nên diện tích chỉ có thể là số nguyên hoặc “x,5”: in bằng s2 / 2 và .5/.0 là chính xác tuyệt đối.

Điểm trong đa giác (ray casting). Từ điểm $P$ kẻ một tia nằm ngang sang phải và đếm số lần tia cắt biên đa giác. Mỗi lần cắt biên là một lần “đổi phe” trong ↔ ngoài, mà ở rất xa bên phải thì chắc chắn ở ngoài. Vậy cắt lẻ lần thì $P$ ở trong, chẵn lần thì ở ngoài.

Hình 4. Đa giác lõm $(1,1), (9,1), (9,6), (6,3), (4,6), (1,5)$. Tia từ $P(2, 4)$ cắt biên 3 lần nên $P$ ở trong; tia từ $Q(7, 5)$ cắt 2 lần nên $Q$ nằm ở “vết lõm”, bên ngoài.

Cài đặt bằng số nguyên: với mỗi cạnh $(a, b)$, cạnh này cắt đường ngang $y = y_P$ khi (a.y > P.y) != (b.y > P.y). Cách viết bất đối xứng này (một đầu tính “lớn hơn”, đầu kia “nhỏ hơn hoặc bằng”) giải quyết gọn trường hợp tia đi qua đúng đỉnh và trường hợp cạnh nằm ngang, không bị đếm hai lần. Giao điểm nằm bên phải $P$ khi $P$ nằm bên trái cạnh hướng lên trên, tức là cross(a, b, P) > 0 nếu $b$ cao hơn $a$, ngược lại thì < 0. Trước đó ta kiểm tra $P$ có nằm trên cạnh không, vì đề thường yêu cầu phân biệt ba trạng thái: trong, ngoài, trên biên.

Xem code C++ / Python: điểm trong đa giác bằng tia (ray casting) (bấm để mở)

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

struct P{ long long x, y; };
int n;
vector<P> poly;

long long cross(P o, P a, P b){
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
bool onSeg(P a, P b, P c){
    return cross(a, b, c) == 0 && min(a.x, b.x) <= c.x && c.x <= max(a.x, b.x)
        && min(a.y, b.y) <= c.y && c.y <= max(a.y, b.y);
}
string locate(P p){
    bool in = false;
    for(int i = 0; i < n; i++){
        P a = poly[i], b = poly[(i + 1) % n];
        if(onSeg(a, b, p)) return "ON";               // nằm trên biên
        if((a.y > p.y) != (b.y > p.y)){               // cạnh vắt qua đường y = p.y
            long long c = cross(a, b, p);
            if(b.y > a.y ? c > 0 : c < 0) in = !in;   // giao điểm nằm bên phải p
        }
    }
    return in ? "IN" : "OUT";
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    poly.resize(n);
    for(auto &p : poly) cin >> p.x >> p.y;
    int m;
    cin >> m;
    while(m--){
        P p;
        cin >> p.x >> p.y;
        cout << locate(p) << "\n";
    }
    return 0;
}

import sys

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

def locate(poly, p):
    n, inside = len(poly), False
    for i in range(n):
        a, b = poly[i], poly[(i + 1) % n]
        c = cross(a, b, p)
        if c == 0 and min(a[0], b[0]) <= p[0] <= max(a[0], b[0]) and min(a[1], b[1]) <= p[1] <= max(a[1], b[1]):
            return 'ON'                                  # nằm trên biên
        if (a[1] > p[1]) != (b[1] > p[1]):               # cạnh vắt qua đường y = p.y
            if (c > 0) if b[1] > a[1] else (c < 0):      # giao điểm nằm bên phải p
                inside = not inside
    return 'IN' if inside else 'OUT'

data = sys.stdin.buffer.read().split()
n = int(data[0])
poly = [(int(data[1 + 2 * i]), int(data[2 + 2 * i])) for i in range(n)]
m = int(data[2 * n + 1])
pos = 2 * n + 2
out = []
for _ in range(m):
    p = (int(data[pos]), int(data[pos + 1])); pos += 2
    out.append(locate(poly, p))
print('\n'.join(out))

Định lý Pick. Với đa giác đơn có mọi đỉnh là điểm nguyên, gọi $I$ là số điểm nguyên nằm hẳn bên trong, $B$ là số điểm nguyên nằm trên biên. Khi đó

$S = I + \dfrac{B}{2} - 1 \quad\Longleftrightarrow\quad 2S = 2I + B - 2.$

$B$ tính dễ: trên cạnh từ $(x_1, y_1)$ tới $(x_2, y_2)$ có đúng $\gcd(|x_2 - x_1|, |y_2 - y_1|)$ điểm nguyên nếu không tính một đầu mút (vì bước nhỏ nhất đi dọc cạnh là $\left(\frac{dx}{g}, \frac{dy}{g}\right)$). Cộng qua mọi cạnh, mỗi đỉnh được tính đúng một lần. Với ngũ giác ở Bảng 2: $2S = 54$, $B = 8$, suy ra $I = (2S - B + 2) / 2 = (54 - 8 + 2) / 2 = 24$ điểm nguyên nằm bên trong. Bước cuối của mô phỏng Shoelace ở trên cũng đếm tay các chấm để em kiểm chứng.

Pick chỉ đúng khi

Mọi đỉnh có toạ độ nguyên và đa giác đơn (không tự cắt, không có lỗ). Đề hỏi “đếm số điểm nguyên bên trong” với toạ độ tới $10^9$ thì không thể đếm từng điểm, Pick là cách duy nhất: chỉ cần Shoelace và gcd, độ phức tạp $O(n \log C)$.

Phần 5Bao lồi bằng thuật toán Andrew (monotone chain)

Bao lồi của một tập điểm là đa giác lồi nhỏ nhất chứa tất cả các điểm. Hình dung mỗi điểm là một chiếc đinh đóng trên bảng, em căng một sợi dây chun bao quanh rồi thả ra: sợi chun ôm sát lấy các đinh ngoài cùng, đó chính là bao lồi. Bài toán “dựng hàng rào ngắn nhất bao quanh mọi cái cây” chính là tìm chu vi bao lồi.

Thuật toán Andrew (monotone chain) dựng bao lồi trong $O(n \log n)$ và cài rất gọn:

1. Sắp xếp các điểm theo $x$ tăng, cùng $x$ thì theo $y$ tăng. Điểm đầu và điểm cuối chắc chắn là đỉnh bao lồi.
2. Chuỗi dưới: duyệt các điểm từ trái sang phải, giữ chúng trong một ngăn xếp h. Trước khi thêm điểm $p$, chừng nào hai điểm cuối của h cùng với $p$ không rẽ trái (cross(h[k-2], h[k-1], p) <= 0) thì bỏ điểm cuối đi, vì nó nằm “lõm vào trong”.
3. Chuỗi trên: làm y hệt nhưng duyệt từ phải về trái, nối tiếp vào cùng ngăn xếp.
4. Điểm cuối cùng của ngăn xếp trùng điểm đầu, bỏ đi. Ta được các đỉnh bao lồi theo chiều ngược kim đồng hồ.

Hình 5. Đi dọc chuỗi dưới (xanh dương) từ trái sang phải, rồi chuỗi trên (cam) từ phải về trái, ta luôn rẽ trái. Điểm nào làm đường đi rẽ phải thì không thể nằm trên bao lồi.

Đây chính là tư tưởng ngăn xếp đơn điệu của bài 25: ngăn xếp luôn giữ một dãy “rẽ trái liên tục”, phần tử nào phá vỡ tính chất ấy bị pop. Mỗi điểm vào ngăn xếp nhiều nhất 2 lần (mỗi chuỗi một lần) và ra nhiều nhất 2 lần, nên sau bước sắp xếp chỉ tốn $O(n)$. Em bấm từng bước để xem các điểm bị loại:

MÔ PHỎNGThuật toán Andrew: dựng chuỗi dưới, chuỗi trên và bỏ điểm rẽ saiNhập tối đa 12 điểm (toạ độ 0 … 10). Mỗi lần ba điểm cuối không rẽ trái, điểm ở giữa bị loại.

Các điểm (x y, …)

ChậmVừaNhanh

điểm đang xétchuỗi dướibộ ba rẽ sai, bị popbao lồi

C++▶ Chạy tay từng dòng codeDựng chuỗi dưới rồi chuỗi trên trong cùng mảng h. Ô vàng ở dãy p: điểm đang xét; dãy h là ngăn xếp các đỉnh tạm thời.

Dữ liệu vào (stdin) – sửa thoải mái7 0 0 4 0 2 1 4 4 1 3 0 4 2 2

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4typedef long long ll;

5typedef pair<ll, ll> P;

6

7ll cross(P o, P a, P b){

8 return (a.first - o.first) * (b.second - o.second) - (a.second - o.second) * (b.first - o.first);

9}

10

11int main(){

12 int n;

13 cin >> n;

14 vector<P> p(n);

15 for(auto &q : p) cin >> q.first >> q.second;

16 sort(p.begin(), p.end());

17 p.erase(unique(p.begin(), p.end()), p.end());

18 n = p.size();

19 if(n == 1){ cout << 1 << "\n" << p[0].first << " " << p[0].second; return 0; }

20 vector<P> h(2 * n);

21 int k = 0;

22 for(int i = 0; i < n; i++){

23 while(k >= 2 && cross(h[k - 2], h[k - 1], p[i]) <= 0) k--;

24 h[k++] = p[i];

25 }

26 for(int i = n - 2, t = k + 1; i >= 0; i--){

27 while(k >= t && cross(h[k - 2], h[k - 1], p[i]) <= 0) k--;

28 h[k++] = p[i];

29 }

30 h.resize(k - 1);

31 cout << h.size() << "\n";

32 for(auto &q : h) cout << q.first << " " << q.second << "\n";

33 return 0;

34}

ChậmVừaNhanhRất nhanh

Xem code C++ / Python: bao lồi bằng thuật toán andrew (bấm để mở)

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

typedef long long ll;
typedef pair<ll, ll> P;                                 // (x, y)

ll cross(P o, P a, P b){
    return (a.first - o.first) * (b.second - o.second) - (a.second - o.second) * (b.first - o.first);
}

vector<P> convexHull(vector<P> p){                      // trả về các đỉnh, ngược chiều kim đồng hồ
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    int n = p.size();
    if(n == 1) return p;
    vector<P> h(2 * n);
    int k = 0;
    for(int i = 0; i < n; i++){                         // chuỗi dưới
        while(k >= 2 && cross(h[k - 2], h[k - 1], p[i]) <= 0) k--;
        h[k++] = p[i];
    }
    for(int i = n - 2, t = k + 1; i >= 0; i--){         // chuỗi trên
        while(k >= t && cross(h[k - 2], h[k - 1], p[i]) <= 0) k--;
        h[k++] = p[i];
    }
    h.resize(k - 1);                                    // điểm cuối trùng điểm đầu
    return h;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<P> p(n);
    for(auto &q : p) cin >> q.first >> q.second;
    vector<P> h = convexHull(p);
    cout << h.size() << "\n";
    for(auto &q : h) cout << q.first << " " << q.second << "\n";
    return 0;
}

import sys

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

def convex_hull(p):                     # trả về các đỉnh, ngược chiều kim đồng hồ
    p = sorted(set(p))
    if len(p) <= 1:
        return p
    def chain(pts):
        h = []
        for q in pts:
            while len(h) >= 2 and cross(h[-2], h[-1], q) <= 0:
                h.pop()                 # rẽ phải hoặc thẳng hàng: bỏ điểm giữa
            h.append(q)
        return h
    lower = chain(p)                    # chuỗi dưới: trái sang phải
    upper = chain(p[::-1])              # chuỗi trên: phải về trái
    return lower[:-1] + upper[:-1]

data = sys.stdin.buffer.read().split()
n = int(data[0])
pts = [(int(data[1 + 2 * i]), int(data[2 + 2 * i])) for i in range(n)]
h = convex_hull(pts)
print(len(h))
print('\n'.join('%d %d' % q for q in h))

Giữ hay bỏ điểm thẳng hàng trên cạnh?

Điều kiện <= 0 bỏ luôn các điểm nằm giữa một cạnh của bao lồi, nên ta chỉ giữ các “góc” thật sự. Nếu đề yêu cầu liệt kê mọi điểm nằm trên biên bao lồi, đổi thành < 0, nhưng khi đó phải cẩn thận trường hợp tất cả các điểm thẳng hàng (chuỗi trên sẽ đi lại đúng các điểm của chuỗi dưới). Và đừng quên xoá điểm trùng trước khi dựng.

Chu vi và diện tích bao lồi. Có danh sách đỉnh $h_0, \ldots, h_{m-1}$ rồi thì diện tích tính bằng Shoelace (phần 4), chu vi là tổng độ dài các cạnh $\sum \sqrt{(x_{i+1} - x_i)^2 + (y_{i+1} - y_i)^2}$. Chu vi là chỗ duy nhất phải dùng số thực: tính bình phương độ dài bằng long long, chỉ chuyển sang double ở bước lấy căn. Nếu mọi điểm thẳng hàng thì bao lồi chỉ có 2 đỉnh, “hàng rào” ôm sát đoạn thẳng nên chu vi bằng hai lần độ dài đoạn, diện tích bằng 0: công thức vòng quanh $h_0 \to h_1 \to h_0$ cho đúng kết quả này mà không cần xét riêng.

Bao lồi còn dùng để làm gì?

Cặp điểm xa nhất: hai điểm xa nhau nhất luôn là hai đỉnh của bao lồi, và có thể tìm bằng hai con trỏ chạy vòng quanh bao lồi (“xoay compa”, bài tập 8). Kiểm tra điểm trong đa giác lồi nhanh trong $O(\log n)$ bằng tìm kiếm nhị phân theo góc. Trong các bài khó hơn, bao lồi còn xuất hiện ở kỹ thuật Convex Hull Trick tối ưu quy hoạch động (sẽ gặp ở series Thuật toán chuyên sâu).

Luyện tập trên web

Các bài dưới đây trên blog đều có lời giải chi tiết bằng C++ và Python, xếp từ dễ tới khó. Em hãy tự làm trước rồi mới xem lời giải nhé.

• Cột bò (Dễ)
• Giải Cứu Đàn Gà (Codeforces 650A Watchmen) (Trung bình)
• Bộ Số Tam Giác (BOSOTG) (HSG12 Đà Nẵng 2018-2019 – Bài 1) (Trung bình)

Xem toàn bộ bài cùng chủ đề: nhãn Hình học.

Bài tậpLuyện hình học tính toán

Bài 1Rẽ trái, rẽ phảiDễ

Một chiếc xe đi lần lượt qua $n$ điểm $P_1, P_2, \ldots, P_n$ ($3 \le n \le 10^5$, toạ độ nguyên, $|x|, |y| \le 10^9$), giữa hai điểm liên tiếp đi theo đường thẳng. Tại mỗi điểm $P_2, \ldots, P_{n-1}$ xe có thể rẽ trái, rẽ phải, hoặc không đổi phương (đi thẳng hoặc quay đầu). Đếm số lần mỗi loại. Dữ liệu vào: dòng đầu là $n$, $n$ dòng sau mỗi dòng một điểm. In ra ba số: số lần rẽ trái, rẽ phải, không đổi phương.

Input

6
0 0
2 0
2 2
4 4
6 2
7 1

Output

1 2 1

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Tại $P_i$ tính cross(P[i-1], P[i], P[i+1]): dương là rẽ trái, âm là rẽ phải, bằng 0 là không đổi phương. Toạ độ tới $10^9$ thì tích có hướng tới $8 \cdot 10^{18}$, vẫn vừa long long. Ví dụ: tại (2, 0): $(2, 0) \times (2, 2) = 4 > 0$, rẽ trái; tại (2, 2): $(0, 2) \times (2, 4) = -4$, rẽ phải; tại (4, 4): $(2, 2) \times (4, 0) = -8$, rẽ phải; tại (6, 2): $(2, -2) \times (3, -3) = 0$, đi thẳng.

Xem code tham khảo (C++ / Python)

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

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> x(n), y(n);
    for(int i = 0; i < n; i++) cin >> x[i] >> y[i];
    int L = 0, R = 0, S = 0;
    for(int i = 1; i + 1 < n; i++){
        long long c = (x[i] - x[i - 1]) * (y[i + 1] - y[i - 1]) - (y[i] - y[i - 1]) * (x[i + 1] - x[i - 1]);
        if(c > 0) L++;
        else if(c < 0) R++;
        else S++;
    }
    cout << L << " " << R << " " << S;
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
x = [int(v) for v in data[1:2 * n + 1:2]]
y = [int(v) for v in data[2:2 * n + 2:2]]
L = R = S = 0
for i in range(1, n - 1):
    c = (x[i] - x[i - 1]) * (y[i + 1] - y[i - 1]) - (y[i] - y[i - 1]) * (x[i + 1] - x[i - 1])
    if c > 0:
        L += 1
    elif c < 0:
        R += 1
    else:
        S += 1
print(L, R, S)

Bài 2Điểm trong tam giácDễ

Cho tam giác $ABC$ không suy biến và $m$ điểm ($m \le 10^5$, mọi toạ độ nguyên, trị tuyệt đối không quá $10^9$). Đếm số điểm nằm trong hoặc trên cạnh tam giác. Dòng đầu gồm 6 số là toạ độ $A, B, C$; dòng hai là $m$; $m$ dòng sau mỗi dòng một điểm.

Input

0 0 6 0 0 6
5
1 1
3 3
4 4
0 7
2 0

Output

3

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Tính ba giá trị cross(A, B, P), cross(B, C, P), cross(C, A, P). Nếu $P$ ở trong, nó nằm cùng một phía với cả ba cạnh (đi vòng $A \to B \to C$) nên ba số cùng dấu; nằm trên cạnh thì có số bằng 0. Vậy $P$ được đếm khi không vừa có số dương vừa có số âm. Cách này không cần biết tam giác cho theo chiều nào. Ví dụ: (1, 1) ở trong, (3, 3) nằm trên cạnh huyền, (2, 0) nằm trên cạnh đáy, còn (4, 4) và (0, 7) ở ngoài.

Xem code tham khảo (C++ / Python)

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

typedef long long ll;
ll cross(ll ox, ll oy, ll ax, ll ay, ll bx, ll by){
    return (ax - ox) * (by - oy) - (ay - oy) * (bx - ox);
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    ll x[3], y[3];
    for(int i = 0; i < 3; i++) cin >> x[i] >> y[i];
    int m, cnt = 0;
    cin >> m;
    while(m--){
        ll px, py;
        cin >> px >> py;
        bool neg = false, pos = false;
        for(int i = 0; i < 3; i++){
            int j = (i + 1) % 3;
            ll c = cross(x[i], y[i], x[j], y[j], px, py);
            if(c < 0) neg = true;
            if(c > 0) pos = true;
        }
        if(!(neg && pos)) cnt++;          // không có cặp dấu trái ngược: trong hoặc trên biên
    }
    cout << cnt;
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
x = [int(data[0]), int(data[2]), int(data[4])]
y = [int(data[1]), int(data[3]), int(data[5])]
m = int(data[6])
cnt = 0
for k in range(m):
    px, py = int(data[7 + 2 * k]), int(data[8 + 2 * k])
    neg = pos = False
    for i in range(3):
        j = (i + 1) % 3
        c = (x[j] - x[i]) * (py - y[i]) - (y[j] - y[i]) * (px - x[i])
        if c < 0:
            neg = True
        elif c > 0:
            pos = True
    if not (neg and pos):               # trong hoặc trên biên
        cnt += 1
print(cnt)

Bài 3Chiều đi của hàng ràoDễ

Một mảnh đất là đa giác đơn có $n$ đỉnh ($3 \le n \le 10^5$, toạ độ nguyên, $|x|, |y| \le 10^6$), các đỉnh được liệt kê lần lượt dọc theo biên. Dòng thứ nhất in CCW nếu các đỉnh được liệt kê ngược chiều kim đồng hồ, CW nếu cùng chiều. Dòng thứ hai in diện tích mảnh đất với đúng một chữ số sau dấu chấm. Dữ liệu đảm bảo diện tích dương.

Input

4
0 0
0 3
5 3
5 0

Output

CW
15.0

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Tính tổng Shoelace chưa lấy trị tuyệt đối: dương là ngược chiều kim đồng hồ, âm là cùng chiều. Diện tích là $|tổng| / 2$, in phần nguyên và “.5” hoặc “.0”. Trong ví dụ, đi từ (0, 0) lên (0, 3) rồi sang phải (5, 3): đó là đi theo chiều kim đồng hồ, tổng bằng $-30$. Với $|x|, |y| \le 10^6$, $2S$ không vượt quá $8 \cdot 10^{12}$ nên long long thừa sức.

Xem code tham khảo (C++ / Python)

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

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    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 s2 = 0;
    for(int i = 0; i < n; i++){
        int j = (i + 1) % n;
        s2 += x[i] * y[j] - x[j] * y[i];
    }
    cout << (s2 > 0 ? "CCW" : "CW") << "\n";      // dấu cho biết chiều đi
    s2 = llabs(s2);
    cout << s2 / 2 << (s2 % 2 ? ".5" : ".0");
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
x = [int(v) for v in data[1:2 * n + 1:2]]
y = [int(v) for v in data[2:2 * n + 2:2]]
s2 = 0
for i in range(n):
    j = (i + 1) % n
    s2 += x[i] * y[j] - x[j] * y[i]
print('CCW' if s2 > 0 else 'CW')        # dấu cho biết chiều đi
s2 = abs(s2)
print(s2 // 2, '.5' if s2 % 2 else '.0', sep='')

Bài 4Đếm cặp đường cắt nhauTrung bình

Có $n$ con đường thẳng, mỗi con đường là một đoạn thẳng ($1 \le n \le 500$, toạ độ nguyên, $|x|, |y| \le 10^9$). Đếm số cặp con đường có ít nhất một điểm chung (kể cả chạm đầu mút hay nằm chồng lên nhau). Mỗi dòng trong $n$ dòng sau dòng đầu gồm 4 số $x_1\ y_1\ x_2\ y_2$.

Input

4
0 0 4 4
0 4 4 0
4 4 6 4
5 0 5 5

Output

3

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Thử mọi cặp $O(n^2)$ với hàm intersect của phần 3, khoảng $1{,}25 \cdot 10^5$ cặp. Với toạ độ $10^9$ bắt buộc lấy dấu từng tích có hướng rồi mới so sánh. Ba cặp có điểm chung: đường 1 và 2 cắt kiểu chữ X tại (2, 2); đường 1 và 3 chạm nhau ở đầu mút (4, 4); đường 3 và 4 cắt nhau tại (5, 4). Đường 2 và đường 3 thì không: đường 3 nằm hẳn bên phải đường 2.

Xem code tham khảo (C++ / Python)

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

struct P{ long long x, y; };

long long cross(P o, P a, P b){
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
int sgn(long long v){ return (v > 0) - (v < 0); }
bool inBox(P a, P b, P c){
    return min(a.x, b.x) <= c.x && c.x <= max(a.x, b.x)
        && min(a.y, b.y) <= c.y && c.y <= max(a.y, b.y);
}
bool intersect(P a, P b, P c, P d){
    int d1 = sgn(cross(a, b, c)), d2 = sgn(cross(a, b, d));
    int d3 = sgn(cross(c, d, a)), d4 = sgn(cross(c, d, b));
    if(d1 * d2 < 0 && d3 * d4 < 0) return true;
    return (d1 == 0 && inBox(a, b, c)) || (d2 == 0 && inBox(a, b, d))
        || (d3 == 0 && inBox(c, d, a)) || (d4 == 0 && inBox(c, d, b));
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<P> a(n), b(n);
    for(int i = 0; i < n; i++) cin >> a[i].x >> a[i].y >> b[i].x >> b[i].y;
    long long cnt = 0;
    for(int i = 0; i < n; i++)
        for(int j = i + 1; j < n; j++)
            if(intersect(a[i], b[i], a[j], b[j])) cnt++;
    cout << cnt;
    return 0;
}

import sys

def intersect(ax, ay, bx, by, cx, cy, dx, dy):
    c1 = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)
    c2 = (bx - ax) * (dy - ay) - (by - ay) * (dx - ax)
    c3 = (dx - cx) * (ay - cy) - (dy - cy) * (ax - cx)
    c4 = (dx - cx) * (by - cy) - (dy - cy) * (bx - cx)
    if ((c1 > 0 and c2 < 0) or (c1 < 0 and c2 > 0)) and ((c3 > 0 and c4 < 0) or (c3 < 0 and c4 > 0)):
        return True
    if c1 == 0 and min(ax, bx) <= cx <= max(ax, bx) and min(ay, by) <= cy <= max(ay, by): return True
    if c2 == 0 and min(ax, bx) <= dx <= max(ax, bx) and min(ay, by) <= dy <= max(ay, by): return True
    if c3 == 0 and min(cx, dx) <= ax <= max(cx, dx) and min(cy, dy) <= ay <= max(cy, dy): return True
    if c4 == 0 and min(cx, dx) <= bx <= max(cx, dx) and min(cy, dy) <= by <= max(cy, dy): return True
    return False

data = sys.stdin.buffer.read().split()
n = int(data[0])
s = [tuple(map(int, data[1 + 4 * i: 5 + 4 * i])) for i in range(n)]
cnt = 0
for i in range(n):
    for j in range(i + 1, n):
        if intersect(*s[i], *s[j]):
            cnt += 1
print(cnt)

Bài 5Trồng cây trong vườnTrung bình

Khu vườn là một đa giác đơn có $n$ đỉnh nguyên ($3 \le n \le 10^5$, $|x|, |y| \le 10^6$). Người ta trồng một cây tại mọi điểm có toạ độ nguyên nằm trên hàng rào (biên) hoặc bên trong khu vườn. In ra hai số: số cây trên hàng rào và số cây nằm hẳn bên trong.

Input

5
1 1
6 0
7 4
3 6
0 3

Output

8 24

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Không thể duyệt từng điểm nguyên (tới $4 \cdot 10^{12}$ điểm). Dùng định lý Pick: $B = \sum \gcd(|dx|, |dy|)$ trên các cạnh, $2S$ từ Shoelace, rồi $I = (2S - B + 2) / 2$. Ví dụ là ngũ giác ở Bảng 2: $2S = 54$, $B = 8$, $I = 24$. Hàm __gcd của C++ nhận long long, Python có math.gcd.

Xem code tham khảo (C++ / Python)

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

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    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 s2 = 0, B = 0;
    for(int i = 0; i < n; i++){
        int j = (i + 1) % n;
        s2 += x[i] * y[j] - x[j] * y[i];
        B += __gcd(llabs(x[j] - x[i]), llabs(y[j] - y[i]));   // điểm nguyên trên cạnh (không tính đầu j)
    }
    s2 = llabs(s2);
    long long I = (s2 - B + 2) / 2;                           // Pick: 2S = 2I + B - 2
    cout << B << " " << I;
    return 0;
}

import sys
from math import gcd

data = sys.stdin.buffer.read().split()
n = int(data[0])
x = [int(v) for v in data[1:2 * n + 1:2]]
y = [int(v) for v in data[2:2 * n + 2:2]]
s2 = B = 0
for i in range(n):
    j = (i + 1) % n
    s2 += x[i] * y[j] - x[j] * y[i]
    B += gcd(abs(x[j] - x[i]), abs(y[j] - y[i]))   # điểm nguyên trên cạnh (không tính đầu j)
s2 = abs(s2)
print(B, (s2 - B + 2) // 2)                         # Pick: 2S = 2I + B - 2

Bài 6Đa giác lồiTrung bình

Cho đa giác đơn (không tự cắt) $n$ đỉnh ($3 \le n \le 10^5$, toạ độ nguyên, $|x|, |y| \le 10^9$), các đỉnh liệt kê lần lượt dọc theo biên, có thể theo chiều bất kỳ. Đa giác có diện tích dương, nhưng có thể có ba đỉnh liên tiếp thẳng hàng. In YES nếu đa giác lồi, ngược lại in NO.

Input

5
0 0
4 0
4 4
2 2
0 4

Output

NO

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Đa giác lồi khi đi dọc biên ta luôn rẽ cùng một phía. Tính cross(P[i], P[i+1], P[i+2]) cho mọi $i$ (chỉ số lấy theo modulo $n$, kể cả hai bộ ba vòng qua đỉnh đầu). Nếu vừa có số dương vừa có số âm thì không lồi; số 0 (ba đỉnh thẳng hàng) không ảnh hưởng. Ví dụ đỉnh (2, 2) tạo “vết lõm”: tại đó đường đi rẽ phải trong khi các đỉnh khác rẽ trái. Điều kiện “đa giác đơn” là cần thiết: ngôi sao năm cánh vẽ một nét luôn rẽ cùng một phía nhưng không lồi.

Xem code tham khảo (C++ / Python)

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

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> x(n), y(n);
    for(int i = 0; i < n; i++) cin >> x[i] >> y[i];
    bool pos = false, neg = false;
    for(int i = 0; i < n; i++){
        int j = (i + 1) % n, k = (i + 2) % n;                 // ba đỉnh liên tiếp i, j, k
        long long c = (x[j] - x[i]) * (y[k] - y[i]) - (y[j] - y[i]) * (x[k] - x[i]);
        if(c > 0) pos = true;
        if(c < 0) neg = true;
    }
    cout << (pos && neg ? "NO" : "YES");
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
x = [int(v) for v in data[1:2 * n + 1:2]]
y = [int(v) for v in data[2:2 * n + 2:2]]
pos = neg = False
for i in range(n):
    j, k = (i + 1) % n, (i + 2) % n        # ba đỉnh liên tiếp i, j, k
    c = (x[j] - x[i]) * (y[k] - y[i]) - (y[j] - y[i]) * (x[k] - x[i])
    if c > 0:
        pos = True
    elif c < 0:
        neg = True
print('NO' if pos and neg else 'YES')

Bài 7Hàng rào quanh khu rừngKhá

Trong rừng có $n$ cái cây ($1 \le n \le 10^5$, toạ độ nguyên, $|x|, |y| \le 10^6$, có thể có cây trùng toạ độ). Cần dựng một hàng rào ngắn nhất bao quanh tất cả các cây (cây có thể nằm sát hàng rào). Dòng thứ nhất in độ dài hàng rào làm tròn 2 chữ số sau dấu chấm, dòng thứ hai in diện tích phần đất được rào với một chữ số sau dấu chấm. Nếu mọi cây thẳng hàng, hàng rào ôm sát đoạn thẳng nên có độ dài gấp đôi đoạn đó và diện tích 0.

Input

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

Output

14.00
12.0

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Dựng bao lồi bằng thuật toán Andrew, rồi đi vòng quanh các đỉnh $h_0 \to h_1 \to \cdots \to h_{m-1} \to h_0$: cộng độ dài từng cạnh (lấy căn của bình phương nguyên) và cộng Shoelace. Bao lồi có 2 đỉnh thì vòng $h_0 \to h_1 \to h_0$ tự cho chu vi gấp đôi đoạn và diện tích 0; bao lồi có 1 đỉnh thì mọi thứ bằng 0. Ví dụ: hai cây (2, 1) và (1, 2) nằm trong hình chữ nhật $4 \times 3$, hàng rào dài $2 \cdot (4 + 3) = 14$, diện tích 12.

Xem code tham khảo (C++ / Python)

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

typedef long long ll;
typedef pair<ll, ll> P;

ll cross(P o, P a, P b){
    return (a.first - o.first) * (b.second - o.second) - (a.second - o.second) * (b.first - o.first);
}
vector<P> convexHull(vector<P> p){
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    int n = p.size();
    if(n == 1) return p;
    vector<P> h(2 * n);
    int k = 0;
    for(int i = 0; i < n; i++){
        while(k >= 2 && cross(h[k - 2], h[k - 1], p[i]) <= 0) k--;
        h[k++] = p[i];
    }
    for(int i = n - 2, t = k + 1; i >= 0; i--){
        while(k >= t && cross(h[k - 2], h[k - 1], p[i]) <= 0) k--;
        h[k++] = p[i];
    }
    h.resize(k - 1);
    return h;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<P> p(n);
    for(auto &q : p) cin >> q.first >> q.second;
    vector<P> h = convexHull(p);
    int m = h.size();
    double per = 0;
    ll s2 = 0;
    for(int i = 0; i < m; i++){
        P a = h[i], b = h[(i + 1) % m];
        ll dx = b.first - a.first, dy = b.second - a.second;
        per += sqrt((double)(dx * dx + dy * dy));
        s2 += a.first * b.second - b.first * a.second;
    }
    printf("%.2f\n%lld%s", per, s2 / 2, s2 % 2 ? ".5" : ".0");
    return 0;
}

import sys
from math import sqrt

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

def convex_hull(p):
    p = sorted(set(p))
    if len(p) <= 1:
        return p
    def chain(pts):
        h = []
        for q in pts:
            while len(h) >= 2 and cross(h[-2], h[-1], q) <= 0:
                h.pop()
            h.append(q)
        return h
    return chain(p)[:-1] + chain(p[::-1])[:-1]

data = sys.stdin.buffer.read().split()
n = int(data[0])
h = convex_hull([(int(data[1 + 2 * i]), int(data[2 + 2 * i])) for i in range(n)])
m = len(h)
per, s2 = 0.0, 0
for i in range(m):
    a, b = h[i], h[(i + 1) % m]
    dx, dy = b[0] - a[0], b[1] - a[1]
    per += sqrt(dx * dx + dy * dy)
    s2 += a[0] * b[1] - b[0] * a[1]
print('%.2f' % per)
print(s2 // 2, '.5' if s2 % 2 else '.0', sep='')

Bài 8Cặp điểm xa nhấtKhá

Cho $n$ điểm ($2 \le n \le 10^5$, toạ độ nguyên, $|x|, |y| \le 10^9$). In ra bình phương khoảng cách lớn nhất giữa hai điểm.

Input

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

Output

50

📝 Nộp bài, chấm tự động trên ClueOJ ↗

💡 Gợi ý

Hai điểm xa nhất luôn là hai đỉnh của bao lồi, nên dựng bao lồi trước. Bao lồi có thể có tới hàng chục nghìn đỉnh, thử mọi cặp $O(m^2)$ vẫn có thể quá chậm. Kỹ thuật xoay compa (rotating calipers): với mỗi cạnh $h_i h_{i+1}$, đỉnh xa cạnh đó nhất là đỉnh $h_j$ làm tam giác $h_i h_{i+1} h_j$ có diện tích (tích có hướng) lớn nhất. Khi $i$ tăng thì $j$ chỉ đi tiếp chứ không lùi, giống hai con trỏ, nên tổng cộng $O(m)$. Ở mỗi bước so sánh $h_j$ với cả $h_i$ và $h_{i+1}$. Ví dụ: bao lồi là (0, 0), (4, −1), (5, 5), (1, 4); cặp xa nhất là (0, 0) và (5, 5) với $5^2 + 5^2 = 50$. Bình phương khoảng cách tới $8 \cdot 10^{18}$ vẫn vừa long long.

Xem code tham khảo (C++ / Python)

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

typedef long long ll;
typedef pair<ll, ll> P;

ll cross(P o, P a, P b){
    return (a.first - o.first) * (b.second - o.second) - (a.second - o.second) * (b.first - o.first);
}
ll d2(P a, P b){
    ll dx = a.first - b.first, dy = a.second - b.second;
    return dx * dx + dy * dy;
}
vector<P> convexHull(vector<P> p){
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    int n = p.size();
    if(n == 1) return p;
    vector<P> h(2 * n);
    int k = 0;
    for(int i = 0; i < n; i++){
        while(k >= 2 && cross(h[k - 2], h[k - 1], p[i]) <= 0) k--;
        h[k++] = p[i];
    }
    for(int i = n - 2, t = k + 1; i >= 0; i--){
        while(k >= t && cross(h[k - 2], h[k - 1], p[i]) <= 0) k--;
        h[k++] = p[i];
    }
    h.resize(k - 1);
    return h;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<P> p(n);
    for(auto &q : p) cin >> q.first >> q.second;
    vector<P> h = convexHull(p);
    int m = h.size();
    if(m == 1){ cout << 0; return 0; }
    if(m == 2){ cout << d2(h[0], h[1]); return 0; }
    ll best = 0;
    for(int i = 0, j = 1; i < m; i++){
        int ni = (i + 1) % m;
        // đẩy j tới khi tam giác (h[i], h[ni], h[j]) không còn to ra
        while(cross(h[i], h[ni], h[(j + 1) % m]) > cross(h[i], h[ni], h[j])) j = (j + 1) % m;
        best = max(best, max(d2(h[i], h[j]), d2(h[ni], h[j])));
    }
    cout << best;
    return 0;
}

import sys

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

def d2(a, b):
    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2

def convex_hull(p):
    p = sorted(set(p))
    if len(p) <= 1:
        return p
    def chain(pts):
        h = []
        for q in pts:
            while len(h) >= 2 and cross(h[-2], h[-1], q) <= 0:
                h.pop()
            h.append(q)
        return h
    return chain(p)[:-1] + chain(p[::-1])[:-1]

data = sys.stdin.buffer.read().split()
n = int(data[0])
h = convex_hull([(int(data[1 + 2 * i]), int(data[2 + 2 * i])) for i in range(n)])
m = len(h)
if m <= 2:
    print(d2(h[0], h[-1]))
else:
    best, j = 0, 1
    for i in range(m):
        ni = (i + 1) % m
        # đẩy j tới khi tam giác (h[i], h[ni], h[j]) không còn to ra
        while cross(h[i], h[ni], h[(j + 1) % m]) > cross(h[i], h[ni], h[j]):
            j = (j + 1) % m
        best = max(best, d2(h[i], h[j]), d2(h[ni], h[j]))
    print(best)

Chuyên đề tiếp theo · Chuyên đề nâng cao 2

Lũy thừa ma trận

Số Fibonacci thứ $10^{18}$, đếm đường đi độ dài $k$ trên đồ thị, quy hoạch động tuyến tính với $n$ khổng lồ: nhân ma trận kết hợp lũy thừa nhanh đưa $O(n)$ về $O(\log n)$.

Học chuyên đề 2 →

← Bài 32: Tổng ôn Thuật toán nâng caoXem cả chuyên đề nâng cao

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇

Bản quyền thuộc về Thầy Nguyễn Việt Nam Sơn. Bài viết, lời giải, hình minh hoạ và mã nguồn trên trang là công sức biên soạn của thầy qua nhiều năm giảng dạy. Vui lòng không sao chép, đăng lại hay sử dụng dưới mọi hình thức khi chưa được sự đồng ý của tác giả. Nếu thấy hữu ích, hãy chia sẻ bằng đường link bài gốc nhé. Cảm ơn bạn!