PHẦN 1. MỞ ĐẦU.....................................................................................................................2
1. LÝ DO CHỌN ĐỀ TÀI......................................................................................................2
2. MỤC ĐÍCH CỦA ĐỀ TÀI..................................................................................................2
3. ĐỐI TƯỢNG NGHIÊN CỨU CỦA ĐỀ TÀI.....................................................................2
3. PHƯƠNG PHÁP NGHIÊN CỨU CỦA ĐỀ TÀI................................................................2
PHẦN 2. NỘI DUNG.................................................................................................................3
I – BIỂU DIỄN CÁC ĐỐI TƯỢNG CƠ BẢN CỦA HÌNH HỌC.........................................3
II. THUẬT TOÁN GIẢI MỘT SỐ BÀI TOÁN HÌNH HỌC CƠ BẢN.................................4
III. MỘT SỐ BÀI TOÁN CƠ BẢN VỀ ĐA GIÁC................................................................9
PHẦN 3. KẾT LUẬN...............................................................................................................19
PHỤ LỤC: MỘT SỐ BÀI TẬP VÍ DỤ.....................................................................................21


PHẦN 1. MỞ ĐẦU
1. LÝ DO CHỌN ĐỀ TÀI
Giải các bài toán có nội dung hình học luôn là một phần quan trọng trong
chương trình tin học hiện nay. Khi giải các bài toán về hình học bằng lập trình,
có một số công việc sẽ xuất hiện với các em học sinh học tin học, đầu tiên là
việc đưa được ra mô hình toán thứ đến nữa là phải chuyển đổi mô hình toán đó
thành chương trình. Có điều khó khăn là, khi giải các bài toán về hình học việc
so sánh giá trị của hai đối tượng nào đó thường phải xử lý dưới dạng số nguyên
(máy tính so sánh hai số thực có khi không chính xác), hơn nữa trong tin học
việc giải các bài toán hình học lại thiên về việc xử lý trên rất nhiều đối tượng vì
vậy cách thức tổ chức dữ liệu, cách thức xây dựng công thức, phương pháp tính
toán là những vấn đề cần hệ thống lại để xây dựng cho các em học sinh có cách
nhìn tổng quan về vấn đề này, giúp các em không bị rối khi lập trình giải các bài
toán hình học. Tuy nhiên các tài liệu như sách giáo khoa Tin học, sách bài tập
Tin học chưa đi sâu vào vấn đề này.
Vì những lý do nói trên nên trong đề tài này tôi đã mạnh dạn trình bày
những kinh nghiệm của mình tích lũy được trong quá trình giảng dạy về lập
trình giải các bài toán hình học, với mong muốn đề tài này có thể có ích cho học

Point = record
x,y : longint
// Đường thẳng, đoạn thẳng
Line = Record
p1, p2 : Point
//Đa giác, tập hợp điểm
Polygon = Array[1..MAXN] of Point
Để thuận lợi thì khi biểu diễn đa giác ta cũng có thể thêm hai đỉnh ở đầu
và cuối: đỉnh 0 bằng đỉnh n và đỉnh n + 1 bằng đỉnh 1.
1

Điều cần lưu ý ở đây là ta có thể dùng hai biến đơn x, y để biểu diễn một
điểm, nhưng nếu như vậy khi càn biểu diễn một tập hợp nhiều điểm ta phải dùng
hai mảng hoặc một mảng hai chiều, điều này sẽ không lợi khi phải sắp xếp các
điểm này theo một thứ tự nào đó.
2

I.2. Kiểu dữ liệu số
Trong các bài toán hình học, phần lớn các đối tượng đều được thể hiện
trên hệ trục tọa độ Descartes, việc biểu diễn các thành phần tọa độ có thể sử
dụng cả kiểu số thực và kiểu số nguyên của ngôn ngữ lập trình. Một số kiểu dữ
liệu của Pascal hay sử dụng.
3

4

+ Kiểu số nguyên:

Tên kiểu



LongInt

-2147483648 → 2147483647

4 byte

5

+ Kiểu số thực:

Tên kiểu

Phạm vi

Dung lượng

Single

1.5×10-45 → 3.4×10+38

4 byte

Real

2.9×10-39 → 1.7×10+38

6 byte

Double

4


7

Function EQA (x,y : doan) : boolean;

8

Begin

9

10

11

EQA := true;
if sqr(x.hc – x.hd) + sqr(x.tc – x.td) = sqr(y.hc – y.hd) + sqr(y.tc –

y.td) .
{ x.hc là hoành độ điểm cuối đoạn x, x.hd là hoành độ điểm đầu

12
15

13

then exit(False)


Nếu k = 0 thì ba điểm A, B, C thẳng hàng, k <0 thì rẽ phải tại B, k > 0 thì
ta có rẽ trái tại B.
21

22

Khi lập trình ta có thể dùng hàm như sau:

23

Function CCW (A,B,C : point) : integer;

24

Begin

25

If (B.x - A.x)*(C.y - B.y) - (B.y - A.y)*(C.x-B.x) = 0 then exit(0);

26

If (B.x - A.x)*(C.y - B.y) - (B.y - A.y)*(C.x-B.x) < 0 then exit(1)

27

Else exit(-1);

5


Function fx (p1,p2,p3 : point) : real;

37

Begin

38

exit(p3.x*(p2.y – p1.y) + p3.y*(p1.x – p2.x) + ( p2.x*p1.y-p1.x*p2.y));

39

End;

II.4. Vị trí tương đối giữa điểm và đường thẳng
40

uuuuuur
Cho 3 điểm P1, P2, M, Vị trí tương đối giữa M và so với vector p1 , p2 , xác

định như sau:
41

VT := (p2.x-p1.x)(M.y-p1.y)-(p2.y-p1.y)(M.x-p1.x);

42

- Nếu VT>0 thì M bên trái véctơ p1 , p2

43


uuuuuu
r

Temp:=(p2.x-p1.x)*(M.y-p1.y)-(p2.y-p1.y)*(M.x-p1.x);
If Temp = 0 then exit(0);

6


If Temp > 0 then exit(1) Else exit(-1);

51

52

53

End; { hàm = 1 thì M bên trái p1 , p2 , hàm = -1 thì M bên phải}

uuuuuu
r

II.5. Xác định điểm M có thuộc đoạn thẳng P1P2
54

M thỏa 2 điều kiện sau:

55



63

End;

II.6. Xác định điểm M có thuộc tia AB
64

uuuu
r

uuur

Điểm M thuộc tia AB nếu M thuộc đường thẳng AB và AM = k . AB với k

≥0:
65

f(M.x,M.y)=0, (M.x-A.x)( B.x-A.x)>=0 và (M.y-A.y)( B.y-A.y)>=0

66

Function PinRay (p1,p2,M : point) : boolean;

67

Var temp : longint;

68



Var temp1, Temp2 : longint;

77

Begin

78

79

Temp1:= PoInLi (p1,p2,M1 : point);
Temp2:= PoInLi (p1,p2,M2 : point) ;

80

Exit(Temp1 *Temp2 >= 0);

81

82

83

End; { hàm = true thì M1, M2 cùng phía, ngược lại thì khác phía}

II.8. Vị trí tương đối của 2 đường thẳng
Cho 4 điểm A, B, C, D. Vị trí tương đối giữa 2 đường thẳng qua 2 điểm
AB và qua 2 điểm CD được xác định như sau:
84

−c2 b2

; dx =

a1 c1
a2 c2

- Nếu (dx=0) and (dy=0) thì trùng nhau - Ngược lại song song.
Function Pos2Li(var I:Point;A,B,C,D: Point): integer;

91

Var a1, b1, c1, a2, b2, c2:real; d, dx, dy: real;

92

Begin

93

94

95

Extract(A,B,a1, b1, c1); // tìm các hệ số a1, b1, c1.
Extract(C,D,a2, b2, c2); // tìm các hệ số a2, b2, c2.

96

d:=a1*b2- a2*b1;

Else // d0

106

107

Begin

108

109

110

111

112

End;

Else exit(-1) // song song

I.x:=dx/d; I.y:=dy/d; exit(1);
End;

0

II.8. Xác định 2 đoạn thẳng có giao nhau hay không
113


III. MỘT SỐ BÀI TOÁN CƠ BẢN VỀ ĐA GIÁC
1. Một số định nghĩa
1.1. Đường gấp khúc
Một đường gấp khúc trên mặt phẳng gồm 1 dãy liên tiếp các đoạn thẳng
[A1,A2], [A2,A3],…, [Ak-1,Ak], mỗi đoạn thẳng được gọi là cạnh, các đầu mút của
các đoạn thẳng gọi là đỉnh.

9


1.2. Đa giác
0
A1.

Một đa giác là một đường gấp khúc khép kín tức điểm A k trùng với điểm

1.3. Đa giác tự cắt
Một đa giác được gọi là tự cắt nếu có hai cạnh không liên tiếp có điểm
chung.
1.4. Đa giác lồi
1
Một đa giác lồi được gọi là lồi nếu đa giác luôn nằm cùng một phía đối
với đường thẳng đi qua một cạnh bất kỳ. Đa giác lồi là đa giác không tự cắt.
1.5. Định lý về bao lồi
2
Với một tập hữu hạn M các điểm trên mặt phẳng(có ít nhất 3 điểm không
thẳng hàng) ta luôn tìm được một tập con H của M sao cho H là tập các đỉnh
của đa giác lồi P mà mọi điểm của M đều thuộc đa giác này.

2. Một số bài toán cơ sở:


126

End;

Exit(abs(S));

Ở đây cần chú ý là P[n+1] trùng với điểm P[1]. Mặt khác cách tính này học
sinh lớp 11 chưa được biết vì vậy khi đưa ra công thức ta có thể không cần
chứng minh để khỏi sa vào dài dòng, quá sức học sinh.
2.2. Kiểm tra đa giác lồi
Kiểm tra dựa theo định nghĩa:

10


127

Function Convex (P:polygon;n:longint):boolean;

128

Var i,j,l,k:longint;

129

Begin
For i:=1 to n do

130


140

End;

141

142

exit(true);

143

End;

2.3. Vị trí tương đối một điểm và đa giác
+ Đối với đa giác lồi
Điểm thuộc đa giác nếu điểm nằm trên các cạnh hoặc thuộc miền đa giác.
Ta thấy nếu xét các cạnh của đa giác theo 1 chiều nào đó thì điểm M thuộc
đa giác nếu nằm cùng 1 bên (trái hoặc phải) với mọi vector cạnh cuả đa giác.

11


144

Function Inside (P:polygon;n:longint;M:point):boolean;

145


end;

155

exit(true);

156

End;

+ Đối với đa giác bất kỳ:

12


- Vẽ trục song với trục tung với tọa độ x=max{các hoành độ}+1.
- Vẽ đoạn thẳng song song với trục hoành và cắt trục vẽ bên trên. Ta nhận
xét nếu số giao điểm với đa giác là số lẻ thì điểm thuộc đa giác. Còn ngược lại
điểm nằm ngoài đa giác.
- Các trường hợp cắt sau ta chỉ tính cắt tại 1 giao điểm:

157

Function Inside (P:polygon;n:longint;M:point):boolean;

158

Var I,count:longint; I,N point; xmax:real;

159


If PoInLi(P[i],P[i+1],M) then exit(true); // M thuộc cạnh

168

If not PoInLi(M,N,P[i]) then

169

Begin
If (not PoInLi(M,N, P[i+1])) and

170

(Intersect(M,N,P[i],P[i+1],I))
13


then inc(count) // trường hợp 3

171
172

Else if not PoInLi(M,N, P[i+2]) and (not
Pos2PoLi(M,N,P[i],P[i+2]))

173

then inc(count); // trường hợp 1


2.4.1. Thuật toán bọc gói
Đây là một giải thuật rất “con người”. Bắt đầu bằng việc chọn một điểm
chắc chắn thuộc bao, dùng một tia quét ngược chiều kim đồng hồ cho đến khi
gặp một điểm khác, ta được thêm một đỉnh thuộc bao, lại tiếp tục với điểm vừa
tìm được…Quá trình kết thúc khi gặp lại đỉnh đầu tiên.
Có nhiều cách chọn điểm đầu tiên, một trong cách đó là ta chọn điểm có
hoành độ nhỏ nhất trong các điểm có tung độ nhỏ nhất.
Một điều đáng chú ý ở đây là việc quét một tia ngược theo chiều kim đồng
hồ để tìm điểm đầu tiên chạm phải thực chất là ta tìm điểm mà tia nối từ điểm
gốc tới nó tạo với trục hoành một góc bé nhất (điều này khá dễ hiểu). Vì vậy
chúng ta cũng cần phải biết cách tính góc khi cho điểm gốc và điểm cần xét đã.
Nhưng chỉ với việc sắp xếp (tìm góc nhỏ nhất) thôi mà phải làm phức tạp đến
vậy thì thật là uổng công. Ta có thể đưa ra một thứ tự hoàn toàn giống với việc
tính góc cụ thể mà chương trình thì đơn giản hơn nhiều:
function Angle(p1, p: Point): Real;
var
dx, dy, ax, ay, t: Real;
begin {p là điểm gốc}
14


dx := p1.x – p.x;
dy := p1.y – p.y;
ax := Abs(dx);
ay := Abs(dy);
if ax + ay < Eps then t := 0
else t := dy/(ax + ay);
if dx < 0 then t := 2 – t
else
if dy < 0 then t := 4 + t;

if (tmp < min) or ((tmp = min) and
(Abs(t.x–p[m].x) < Abs(p[i].x–p[m].x))) then
begin {nếu nhiều điểm thoả mãn, chọn điểm ở xa nhất}
min := tmp;
li := i;
t := p[i];
end;
end;
until li = n + 1;
end;

2.4.2.Thuật toán Grahamscan
Thuật toán bọc gói đòi hỏi một chi phí là O(M*N) (trong đó M là số điểm
trên bao). Vì vậy nó chỉ làm việc tốt trong trường hợp số điểm nằm trên bao nhỏ
hơn nhiều so với tổng số. Nhưng trong trường hợp xấu nhất (tất cả mọi điểm đều
nằm trên bao) thì chi phí thuật toán sẽ lên tới O(N 2). Chúng ta sẽ tiếp cận một
phương pháp tốt hơn – phương pháp quét Graham. Phương pháp này có chi phí
thuật toán ổn định và không tốn kém lắm. Hầu như tất cả chi phí là dành cho
việc khởi một tạo đường khép kín đơn từ tập điểm đã cho.
Chọn điểm chốt có hoành độ x lớn nhất trong các điểm có tung độ y nhỏ
nhất (khi hiểu rõ thuật toán các bạn sẽ biết được nguyên nhân). Chuyển điểm
chốt về vị trí 1 để tiện cho tính toán. Ta sắp xếp các điểm theo khoá là góc tạo
bởi điểm đó và điểm chốt với trục hoành theo thứ tự tăng dần. Khi đi theo thứ tự
p[1], p[2], …p[N], p[1] ta thu được một đa giác khép kín đơn.
Ta đi vòng quanh đa giác này, thử đặt một điểm vào bao và kiểm tra xem
các điểm trước đó có còn nằm trên bao hay không. Nếu không ta chỉ việc loại
các điểm đó ra khỏi bao.Việc kiểm tra một điểm có còn nằm trên bao hay không
có thể làm như sau: Khi cho một điểm mới vào bao, ta sẽ lần ngược lại những
điểm đã nằm trong bao. Trong quá trình, nếu gặp một điểm là khúc rẽ phải thì
điểm này sẽ không thuộc bao nữa, ta loại nó luôn. Quá trình kết thúc khi ta gặp

m := 2;
for i := 3 to n do
begin
while CCW(p[m - 1], p[m], p[i]) 1 do Dec(m);
Inc(m);
p[m] := p[i];
end;
end;

17


Chi phí cho thủ tục trên tỷ lệ thuận với N. Đúng vậy, mặc dù trong vòng
lặp có một vòng lặp, nhưng ta để ý là không điểm nào bị loại quá một lần nên
vòng lặp này chỉ hoạt động không đến N lần.
Như vậy chi phí cho thuật toán này là O(NlogN) nếu ta dùng phương pháp
sắp xếp tốt (như Quick Sort chẳng hạn).
Ta có thể làm giảm chi phí tính toán đi rất nhiều bằng cách loại bỏ những
điểm chắc chắn không thuộc bao.
Ví dụ như ta loại đi những điểm nằm hoàn toàn trong tứ giác có các đỉnh
là các điểm có hoành độ lớn nhất, hoành độ nhỏ nhất, tung độ lớn nhất, tung độ
nhỏ nhất. Đối với những bộ dữ liệu được tạo một cách ngẫu nhiên thì việc này
rất có ích. Nhưng nếu tất cả các điểm đều thuộc bao thì việc này là vô nghĩa. Nói
chung mọi cách tham lam thì cũng đều tốt trong một số trường hợp nhất định mà
thôi.

18


PHẦN 3. KẾT LUẬN

viết, không sao chép nội dung của người
khác.

Nghiêm Quang Khải

19


Tài liệu tham khảo
1. Tài liệu tập huấn phát triển chuyên môn giáo viên Tin học - Nhiều tác
giả
2. Chuyên đề hình học – Một số vấn đề phát triển môn Tin học – Nguyễn
Xuân My
3. VNOI - Olympic tin học Việt Nam
4. Website:

20


PHỤ LỤC: MỘT SỐ BÀI TẬP VÍ DỤ
Bài 1. HÌNH CHỮ NHẬT
Xét các hình chữ nhật kích thước w×h, trong đó w, h – nguyên và w > h.
Một hình chữ nhật gọi là nhỏ hơn hình chữ nhật khác nếu thỏa mãn một trong 2
điều kiện:
• Có đường chéo ngắn hơn,
• Có đường chéo bằng nhau, nhưng có độ cao h nhỏ hơn.

Đường
chéo


47
28
98 100
3 140
99 100
89 109
00
Thuật toán: Bài này đơn giản là sử dụng công thức tính đường chéo hình
chữ nhật, sau đó duyệt lần lượt để tính. Độ phức tạp O(w*h) cho 1 test .
21


Bài 2: Đa giác
Trên mặt phẳng tọa độ, xét đa giác lồi n đỉnh, các đỉnh đều có tọa độ nguyên và
có giá trị tuyệt đối không vượt quá 105. Các đỉnh của đa giác được liệt kê theo
chiều kim đồng hồ.
Yêu cầu: Cho đoạn thẳng xác định bởi hai điểm có tọa độ là (x1, y1) và (x2, y2)
trong đó x1, y1, x2, y2 là các số nguyên và có giá trị tuyệt đối không vượt quá
105. Hãy xác định độ dài L là phần của đoạn thẳng nằm trong đa giác hay trên
cạnh của đa giác và đưa ra số nguyên là phần nguyên của tích (L * 100).
Dữ liệu: vào từ file văn bản “DG.INP” có dạng:
• Dòng đầu tiên chứa số nguyên n (3 ≤ n ≤ 100)
• Dòng thứ i trong n dòng sau chứa 2 số nguyên xác định tọa độ đỉnh i của
đa giác,
• Dòng cuối cùng chứa 4 số nguyên x1, y1, x2, y2.
Hai số liên tiếp trên một dòng cách nhau một dấu cách.
Kết quả: ghi ra file văn bản “DG.OUT” một số nguyên là phần nguyên của tích
(L*100).
Ví dụ:
DG.INP

• N - 3 dòng tiếp theo, mỗi dòng ghi hai số nguyên dương i, j cho biết có sử
dụng đường chéo nối đỉnh i với đỉnh j trong phép phân hoạch tìm được
• Các số trên một dòng của Input/Output file được ghi cách nhau ít nhất
một dấu cách.
Giới hạn:
• N nguyên dương, 4 ≤ n ≤ 100
• Các toạ độ đỉnh là số thực: Xi, Yi≤ 106
• Trọng số của phép tam giác phân nhỏ nhất được ghi dưới dạng số thực
làm tròn lấy 6 chữ số sau dấu chấm thập phân.
Ví dụ:
POLYGON.INP POLYGON.OUT
y
6
12.000000
40
26
51
24
65
46
25
03
21
0

x

Thuật toán: Đây là một bài toán giải theo phương pháp quy hoạch động
hình học. Kiến thức hình học sử dụng để giải bài toán này là về khoảng cách
giữa hai điểm trên mặt phẳng.

End;
Function dis(i,j: longint): double;
Begin
if (abs(i-j)=1) then exit(0);
exit(sqrt((sqr(p[i].x-p[j].x)+sqr(p[i].y-p[j].y))))
End;
Function d_p(i,j: longint): double;
Var k: longint;
Begin
if abs(i-j)
type
m1=array[0..nmax] of real;
m2=array[0..nmax] of longint;
var
n: longint;
x,y,qx:m1;
c:m2;
sl: longint;
25