Điểm, khoảng cách và tích có hướng

Mức độ: Cơ bản

Bài toán hình học trong đề thi lập trình thường cho tọa độ các điểm. Thay vì vẽ hình, ta tính toán bằng các phép cộng, trừ, nhân trên tọa độ. Bí quyết quan trọng nhất: làm việc hoàn toàn bằng số nguyên khi có thể, vì số thực có sai số làm tròn.

Điểm và vectơ

Điểm A có tọa độ (x_A, y_A). Vectơ AB là “bước đi” từ A đến B: AB = (x_B - x_A, y_B - y_A).

Khoảng cách

Theo định lý Pythagore, khoảng cách AB = √((x_B - x_A)² + (y_B - y_A)²).

Mẹo: nếu chỉ cần so sánh khoảng cách (điểm nào gần hơn), hãy so sánh bình phương khoảng cách (số nguyên), không cần lấy căn. AB nhỏ hơn AC khi và chỉ khi AB² nhỏ hơn AC².

Hai loại khoảng cách khác hay gặp trên lưới ô vuông:

Cách đi	Khoảng cách từ (0, 0) đến (3, 4)
đường chim bay	√(9 + 16) = 5
chỉ đi ngang, dọc (Manhattan): \|dx\| + \|dy\|	7
đi cả đường chéo như quân vua: max(\|dx\|, \|dy\|)	4

Tích vô hướng: kiểm tra vuông góc

Với hai vectơ u = (a, b) và v = (c, d), tích vô hướng u · v = a × c + b × d.

u · v = 0 khi hai vectơ vuông góc.
u · v dương: góc giữa chúng nhọn; u · v âm: góc tù.

Tích có hướng: rẽ trái hay rẽ phải

Tích có hướng của u = (a, b) và v = (c, d) là u × v = a × d - b × c (một số nguyên). Đứng ở A nhìn về B, điểm C nằm:

Dấu của AB × AC	C nằm ở	Đi A → B → C thì
dương	bên trái	rẽ trái (ngược chiều kim đồng hồ)
âm	bên phải	rẽ phải (cùng chiều kim đồng hồ)
bằng 0	trên đường thẳng AB	thẳng hàng

Ví dụ A = (0, 0), B = (4, 0), C = (1, 3): AB = (4, 0), AC = (1, 3), AB × AC = 4 × 3 - 0 × 1 = 12, dương: C ở bên trái (phía trên) đường AB.

Ý nghĩa diện tích: |AB × AC| bằng hai lần diện tích tam giác ABC. Tam giác trên có diện tích 12 / 2 = 6 (đáy 4, chiều cao 3).

Python
C++

def tich_co_huong(a, b, c):
    # AB × AC: > 0 rẽ trái, < 0 rẽ phải, = 0 thẳng hàng
    return (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0])

A, B, C = (0, 0), (4, 0), (1, 3)
t = tich_co_huong(A, B, C)
print(t, abs(t) / 2)          # 12 6.0

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

long long tichCoHuong(long long ax, long long ay, long long bx, long long by, long long cx, long long cy) {
    // AB × AC: > 0 rẽ trái, < 0 rẽ phải, = 0 thẳng hàng
    return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax);
}

int main() {
    long long t = tichCoHuong(0, 0, 4, 0, 1, 3);
    cout << t << " " << llabs(t) / 2.0 << endl;   // 12 6
    return 0;
}

Lưu ý: với tọa độ tới 10⁹, tích có hướng tới khoảng 4 × 10¹⁸, vẫn vừa long long, nhưng không được dùng int.

Ứng dụng của tích có hướng

Ba điểm thẳng hàng: AB × AC = 0. Đây chính là phép kiểm tra đã dùng ở bài tam giác trên lưới điểm.
Điểm trong tam giác: P nằm trong tam giác ABC khi P nằm cùng một phía với cả ba cạnh (ba tích có hướng AB × AP, BC × BP, CA × CP cùng dấu).
Hai đoạn thẳng cắt nhau: đoạn AB và CD cắt nhau khi C, D nằm hai bên đường AB và A, B nằm hai bên đường CD (bài 13).

Luyện tập

Gồm 22 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. Khoảng cách

Bài 1. Điểm nào gần hơn

Nhập tọa độ nguyên của ba điểm A, B, C (giá trị tuyệt đối ≤ 10⁹), mỗi điểm một dòng. In ra B nếu B gần A hơn C, C nếu C gần A hơn B, BANG nếu cách đều.

Ví dụ:

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

Kiểm tra: nhập

1 1
-2 5
6 2

Xem đáp số

B

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

Bài 2. Khoảng cách Manhattan

Một người đi trong thành phố có các con đường kẻ ô vuông, chỉ đi theo phương ngang hoặc dọc. Nhập tọa độ nguyên hai điểm (giá trị tuyệt đối ≤ 10⁹), in ra quãng đường ngắn nhất.

Ví dụ:

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

Kiểm tra: nhập

-5 7
12 -3

Xem đáp số

27

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

Bài 3. Quân vua đi

Quân vua trên bàn cờ vô hạn mỗi bước đi sang một trong 8 ô xung quanh. Nhập tọa độ ô xuất phát và ô đích (giá trị tuyệt đối ≤ 10⁹), in ra số bước ít nhất.

Ví dụ:

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

Kiểm tra: nhập

-5 7
12 -3

Xem đáp số

17

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

Bài 4. Cặp điểm gần nhau nhất

Dòng đầu là n (2 ≤ n ≤ 3000). n dòng tiếp theo là tọa độ nguyên các điểm (giá trị tuyệt đối ≤ 10⁶). In ra bình phương khoảng cách nhỏ nhất giữa hai điểm.

Ví dụ:

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

Kiểm tra: nhập

Xem đáp số

13

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

Bài 5. Điểm xa gốc tọa độ nhất

Dòng đầu là n (n ≤ 10⁵). n dòng tiếp theo là tọa độ nguyên các điểm (giá trị tuyệt đối ≤ 10⁹). In ra số thứ tự (từ 1) của điểm xa gốc O(0, 0) nhất; nếu nhiều điểm cùng xa nhất thì in số nhỏ nhất.

Ví dụ:

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

Kiểm tra: nhập

Xem đáp số

5

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

Nhóm 2. Tích vô hướng, tích có hướng

Bài 6. Rẽ trái hay rẽ phải

Nhập tọa độ nguyên ba điểm A, B, C (giá trị tuyệt đối ≤ 10⁹), mỗi điểm một dòng. Đi từ A đến B rồi đến C: in ra TRAI, PHAI hoặc THANG HANG.

Ví dụ:

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

Kiểm tra: nhập

1 1
5 3
7 2

Xem đáp số

PHAI

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

Bài 7. Diện tích tam giác

Nhập tọa độ nguyên ba đỉnh của một tam giác (giá trị tuyệt đối ≤ 10⁹). In ra diện tích tam giác, viết đúng một chữ số sau dấu chấm (diện tích luôn có dạng số nguyên hoặc ,5).

Ví dụ:

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

Kiểm tra: nhập

-3 2
5 -1
2 7

Xem đáp số

27.5

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

Bài 8. Ba điểm thẳng hàng

Nhập tọa độ nguyên ba điểm (giá trị tuyệt đối ≤ 10⁹). In ra YES nếu ba điểm thẳng hàng, ngược lại NO.

Ví dụ:

Nhập	In ra
`1 1` `2 2` `5 6`	`NO`

Kiểm tra: nhập

-1000000000 -999999999
0 1
1000000000 1000000001

Xem đáp số

YES

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

Bài 9. Điểm trong tam giác

Dòng đầu là tọa độ ba đỉnh tam giác (6 số), dòng thứ hai là tọa độ điểm P (giá trị tuyệt đối ≤ 10⁶). In ra TRONG, TREN CANH hoặc NGOAI.

Ví dụ:

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

Kiểm tra: nhập

0 0 6 0 0 6
3 3

Xem đáp số

TREN CANH

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

Bài 10. Tam giác vuông

Nhập tọa độ nguyên ba đỉnh tam giác (không thẳng hàng, giá trị tuyệt đối ≤ 10⁹). In ra YES nếu tam giác vuông, ngược lại NO.

Ví dụ:

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

Kiểm tra: nhập

1 2
4 6
8 3

Xem đáp số

YES

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

Bài 11. Tứ giác lồi

Nhập tọa độ nguyên 4 đỉnh A, B, C, D của một tứ giác theo thứ tự đi quanh (không có ba điểm thẳng hàng, các cạnh không cắt nhau). In ra LOI nếu tứ giác lồi, ngược lại LOM.

Ví dụ:

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

Kiểm tra: nhập

Xem đáp số

LOM

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

Nhóm 3. Đường thẳng và đoạn thẳng

Bài 12. Điểm nằm trên đoạn thẳng

Dòng đầu là tọa độ hai đầu đoạn thẳng AB (4 số), dòng thứ hai là tọa độ điểm P (giá trị tuyệt đối ≤ 10⁹). In ra YES nếu P nằm trên đoạn AB (kể cả hai đầu), ngược lại NO.

Ví dụ:

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

Kiểm tra: nhập

0 0 4 4
6 6

Xem đáp số

NO

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

Bài 13. Hai đoạn thẳng cắt nhau

Nhập tọa độ nguyên 4 điểm A, B, C, D (mỗi điểm một dòng, giá trị tuyệt đối ≤ 10⁹). In ra YES nếu đoạn AB và đoạn CD có điểm chung, ngược lại NO.

Ví dụ:

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

Kiểm tra: nhập

Xem đáp số

NO

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

Bài 14. Phương trình đường thẳng

Nhập tọa độ nguyên hai điểm khác nhau A, B (giá trị tuyệt đối ≤ 10⁹). In ra ba số nguyên a, b, c của phương trình đường thẳng AB dạng a × x + b × y = c, với a, b, c không có ước chung lớn hơn 1 và a dương (hoặc a = 0 và b dương).

Ví dụ:

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

Kiểm tra: nhập

1 3
7 -1

Xem đáp số

2 3 11

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

Bài 15. Vị trí hai đường thẳng

Nhập 4 điểm A, B, C, D (tọa độ nguyên, A khác B, C khác D, giá trị tuyệt đối ≤ 10⁹). In ra CAT nếu đường thẳng AB và CD cắt nhau tại đúng một điểm, SONG SONG nếu song song, TRUNG nếu trùng nhau.

Ví dụ:

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

Kiểm tra: nhập

Xem đáp số

TRUNG

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

Bài 16. Giao điểm hai đường thẳng

Nhập 4 điểm A, B, C, D (tọa độ nguyên, giá trị tuyệt đối ≤ 10⁶), đảm bảo đường thẳng AB và CD cắt nhau. In ra tọa độ giao điểm dưới dạng hai phân số tối giản p/q (mẫu dương; nếu là số nguyên vẫn ghi mẫu 1).

Ví dụ:

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

Kiểm tra: nhập

Xem đáp số

28/17 7/17

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

Nhóm 4. Vận dụng

Bài 17. Giao của hai hình chữ nhật

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

Ví dụ:

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

Kiểm tra: nhập

-5 -5 5 5
0 -10 3 2

Xem đáp số

21

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

Bài 18. Đếm điểm trong hình chữ nhật

Dòng đầu là n (n ≤ 10⁵). n dòng tiếp theo là tọa độ các điểm. Dòng cuối là x1 y1 x2 y2 của một hình chữ nhật cạnh song song trục. Đếm số điểm nằm trong hoặc trên cạnh hình chữ nhật.

Ví dụ:

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

Kiểm tra: nhập

Xem đáp số

4

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

Bài 19. Bốn điểm tạo hình vuông

Nhập tọa độ nguyên 4 điểm khác nhau (giá trị tuyệt đối ≤ 10⁹, thứ tự bất kỳ). In ra YES nếu 4 điểm là 4 đỉnh của một hình vuông (có thể xoay nghiêng), ngược lại NO.

Ví dụ:

Nhập	In ra
`0 0` `1 1` `1 0` `0 1`	`YES`

Kiểm tra: nhập

Xem đáp số

YES

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

Bài 20. Robot theo lệnh

Robot ở gốc tọa độ, nhận một xâu lệnh gồm N (lên), S (xuống), E (sang phải), W (sang trái), mỗi lệnh đi 1 ô (độ dài ≤ 10⁵). In ra tọa độ cuối cùng và bình phương khoảng cách lớn nhất tới gốc mà robot đạt được trong quá trình đi.

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

Kiểm tra: nhập NNNEESWWWWSSSE.

Xem đáp số

-1 -1 13

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

Bài 21. Chu vi đ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 đa giác theo thứ tự đi quanh, mỗi cạnh song song với một trục tọa độ. In ra chu vi.

Ví dụ:

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

Kiểm tra: nhập

Xem đáp số

22

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

Bài 22. Nhiều điểm thẳng hàng nhất

Dòng đầu là n (1 ≤ n ≤ 1000). n dòng tiếp theo là tọa độ nguyên các điểm khác nhau. In ra số điểm nhiều nhất cùng nằm trên một đường thẳng.

Ví dụ:

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

Kiểm tra: nhập

Xem đáp số

4

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