SỞ GIÁO DỤC VÀ ĐÀO TẠO NAM ĐỊNH
TRƯỜNG TRUNG HỌC PHỔ THÔNG CHUYÊN LÊ HỒNG PHONG
NAM ĐỊNH
SÁNG KIẾN DỰ THI CẤP TỈNH

BÁO CÁO SÁNG KIẾN

ỨNG DỤNG VECTO
VÀO GIẢI QUYẾT
MỘT SỐ BÀI TOÁN HÌNH HỌC
TRONG TIN HỌC

Tác giả: Đỗ Thị Minh Hường
Trình độ chuyên môn: Thạc sỹ
Chức vụ: giáo viên
Nơi công tác: trường trung học phổ thông chuyên
Lê Hồng Phong Nam định

Nam định, ngày 15 tháng 5 năm 2015
1


1.Tên sáng kiến:
Ứng dụng vecto vào giải quyết một số bài toán hình học trong tin học.
2. Lĩnh vực áp dụng sáng kiến:
Các trường THPT chuyên dạy cho học sinh chuyên và tập huấn cho học
sinh dự kỳ thi học sinh giỏi Quốc gia môn Tin học Lớp 12.
3. Thời gian áp dụng sáng kiến: từ năm 2010 đến 2015
4.Tác giả:
Họ và tên: Đỗ Thị Minh Hường
Năm sinh: 1973

em hầu hết đều không tốt và đặc biệt là chưa có phương pháp học kế thừa
những đơn vị kiến thức đã học. Tất cả những vấn đề giáo viên đưa ra hoặc đọc
tài liệu hầu như các em đều cho là mới tinh và chưa biết tìm hiểu những vấn
đề này được xây dựng và kế thừa từ những đơn vị kiến thức nào đã học để suy
luận và từ đó có thể đưa ra những vấn đề mới được tổng hợp từ những vấn đề
đã biết. Chính vì vậy, tôi xây dựng hệ thống chuyên đề về vecto được biết
trong toán học và phương pháp biểu biễn trong tin học các yếu tố hình học
trong lập trình dưới dạng kế thừa các đơn vị kiến thức đã biết, giúp học sinh
có thể đọc, hiểu và đặc biệt là làm quen phương pháp biết kế thừa những kiến
thức cũ để xây dựng lý thuyết mới và đặc biệt là giúp các em có một phương
pháp giải quyết một số bài toán hình học trong kì thi học sinh giỏi các cấp.
2. Mô tả giải pháp sau khi có sáng kiến

3


Hình học đối với giác quan của con người thì khá quen thuộc và dễ dàng.
Nhưng hình học đối với máy tính thì lại là một vấn đề khác. Nhiều bài toán ta
có thể giải ngay lập tức bằng cách “nhìn vào hình vẽ ta thấy”, nhưng để thể
hiện trên máy tính thì cần những chương trình không đơn giản chút nào.
Các giải thuật hình học thường là các giải thuật đẹp và đôi khi là rất bất
ngờ. Thực vậy, những tưởng có những bài toán ta phải giải quyết với chi phí
thuật toán rất lớn (đôi khi không thể chấp nhận được), nhưng nhờ vào chính
những tính chất đặc biệt của hình học mà ta lại có thể giải quyết nó một cách
dễ dàng và “đẹp mắt”.
A. Một số khái niệm cơ bản
1. Hệ tọa độ Đề các

r r


uuur
+) Tọa độ vectơ AB = ( xB − x A ; yB − y A )
 x A + xB y A + y B 
;
÷
2 
 2

+) I là trung điểm AB thì tọa độ I 

4


+) Độ dài đoạn thẳng AB = ( xA − xB ) + ( y A − yB )
2

2

- Hai phép toán đối với hai vecto

r

r

+) Tích chấm (tích vô hướng) của hai vecto: Cho hai vecto u và v , tích vô
r

r

r r


(

xu .xv + yu . yv

)

x + yu2 . xv2 + yv2
2
u

r

r

+) Góc định hướng giữa hai vecto: Cho hai vecto u và v , góc định hướng
r

r

giữa hai vecto u và v là góc lượng giác giữa hai vecto này, dấu của góc là
r

r

dương nếu chiều từ u đến v là ngược chiều kim đồng hồ và mang dấu âm
theo chiều ngược lại.

r


=
x
;
y
;
v
=
x
;
y
(
)
(
)
Nếu tọa độ của
thì × v = xu . yv − xv . yu =
u
u
v
v
yu

xv
yv
r

Từ công thức trên ta có thể tính được sin của góc định hướng giữa hai vecto u
r

và v

r r

Cho hai hệ tọa độ trực chuẩn trên mặt phẳng (O; i ; j ) và (O’;

r ur
r ur
i ' ; j ' ). Giả sử điểm M có tọa độ M(x; y) đối với hệ tọa độ (O’; i ' ; j ' ). Hãy
r r
xác định tọa độ điểm M đối với hệ tọa độ (O; i ; j )?

Giải

r r

r

Giả sử trong hệ tọa độ (O; i ; j ), điểm O’ có tọa độ O’(p, q), vecto i '
ur

=(a; b); j ' = (c; d)
Khi đó ta có:

uuuur
r r
OO ' = p.i + q. j
r
r r
i ' = a.i + b. j
ur r
r

r r

r

)

ur

(

)

Giả sử trong hệ tọa độ (O; i ; j ) điểm O’(p; q); i ' =(a; b); j ' =(c; d) và M(
x; y ) .

6


 x = a.x + c. y + p

r ur

Trong hệ tọa độ (O’; i ' ; j ' ) điểm M(x; y) và thì 

 y = b.x + d . y + q

4. Xây dựng công thức biến đổi tọa độ
Trong hình học phẳng có các phép biến hình nhằm biến đổi từ hình này
sang hình khác đồng dạng với nó. Các phép biến hình này rất quan trọng trong
việc thiết kể các bài toán liên quan đến hình trong tin học. Ở đây ta nghiên

 x = − y
+) Góc α = 90 ta có công thức đổi trục là: 
 y = x
 x = − x
+) Góc α = 1800 ta có công thức đổi trục là: 
 y = − y
0

4.2. Phép tịnh tiến

7


Xét phép tịnh tiến theo vecto (a; b). Phép tịnh tiến này biến điểm O(0;
0) thành điểm O’(a; b), điểm I(1; 0) biến thành điểm I’(a+ 1; b) và điểm J(0;1)
biến thành điểm J’(a; b+1)

uuuur

uuuuur

Khi đó ta có: O’(a; b) ; O ' I ' = (1; 0); O ' J ' = (0;1)
 x = x + a

Áp dụng công thức đổi trục tọa độ ta có 

 y = y + b

5. Biểu diễn các yếu tố trong hình học
5.1 Đường thẳng



5.3. Tia:
Để biểu diễn tia Ax, ta quan tâm tới gốc A và 1 vecto chỉ hướng của tia
hoặc có thể biểu diễn bởi gốc A và một điểm B nằm trên tia.
5.4. Đa giác:
Đa giác là một đường gấp khúc khép kín.
Để biểu diễn đa giác trên máy tính ta lưu một dãy các đỉnh liên tiếp
nhau.
B. Một số bài toán cơ bản
1. Cài đặt một số phép toán cơ bản trên vecto
Uses math;
Type
Real = Extended;
Tpoint = record
x, y : real;
End;
Tvecto = Tpoint;
Const

eps : real=1e-3;

----Phép toán tích chéo của hai vecto--Operator

>
r

r

r

 a1 p + b1q = c1

Khi đó c = p.a + q.b ⇔ a p + b q = c (I)
 2
2
2
Do đó vấn đề cần giải quyết của bài toán trở thành tìm nghiệm của hệ
(I) với ẩn là p và q.
Để giải quyết vấn đề này ta tính ba định thức
D=
Dp =
Dq =

a1 a 2
b1

b2

c1 c 2
b1

b2

a1 a 2

- Dp= Dq = 0 thì hệ vô số nghiệm, khi đó c cùng phương với cả hai vecto
r r
a , b . Khi đó hệ có nghiệm (p; q) =(Nan; Nan)

10


r

- Dp ≠ 0 hoặc Dq ≠ 0 thì hệ vô nghiệm, khi đó c không cùng phương với
r r

hai vecto a , b . Khi đó hệ có nghiệm (p; q) = (Inf; Inf)
Cài đặt
function
var

bdtt(const

a, b, c : tvecto):Tvecto;

d : float;

begin
D:=a>< b;
result:=vector((c><b)/D,(a>

Một cách giải quyết khác có thể hiệu quả hơn là: Nếu hai đoạn thẳng
AB và CD cắt nhau tại M thì sẽ tồn tại duy nhất một cặp số (p; q) thuộc đoạn
uuuur
uuur
 AM = p AB
[0; 1] sao cho:  uuuur uuur (1)
CM = qCD
uuuur uuuur
uuur uuur
uuur
uuur uuur
Từ (1) ⇒ AM − CM = p AB + qDC hay AC = p AB + qDC

uuur

Khi đó, bài toán trở thành : tìm biểu diễn tuyến tính của AC qua hai

uuur

uuur

vecto AB và DC , sau đó kiểm tra cặp số (p; q) ∈[0; 1], nếu thỏa mãn thì tọa độ
uuuur uuur

uuur

điểm M được tìm theo đẳng thức sau: OM = OA + p AB
5. Tìm giao điểm giữa một đoạn thẳng và một tia


(7a)
2

12


+)Với tọa độ ba đỉnh A(xA; yA); B(xB; yB); C(xC; yC) thì công thức (7a)
có thể viết theo tọa độ S =

( xB − xA ) ( yC − y A ) − ( xC − xA ) ( yB − y A )
2

(7b)

7.Đa giác
7.1. Diện tích đa giác
Bài toán 5:

Trên mặt phẳng với hệ tọa độ Đêcác vuông góc, cho đa giác

P= P1P2…Pn , trong đó các điểm Pi có tọa độ tương ứng là (xi; yi). Tính diện
tích đa giác P?
Giải quyết
* Ta bổ sung thêm điểm P0 ≡ Pn và điểm Pn+1 ≡ P1.
Khi diện tích đa giác P được tính bằng công thức
S=

1
2


1 2

2 3

3 4

4 1

Mà theo phần trên (diện tích tam giác) ta thấy
uuur

uuur

+) Quay vecto OP1 tới vecto OP2 là hướng thuận nên theo công thức (7a) thì
S ∆OP1P2 mang dấu âm

+) Tương tự như vậy S∆OP P mang dấu âm con S∆OP P và S∆OP P mang dấu
2 3

3 4

4 1

dương.
Khi đó, ta thấy diện tích đa giác là
uuur uuuuur 1  n uuur uuuuur 
1 uuur uuur uuur uuur
OP
×
OP



Tóm lại, tổng quát trong trường hợp các đỉnh của đa giác được đánh theo
chiều thuận hay nghịch thì ta đều có thể tính diện tích đa giác P bằng công
thức sau: S =

1
2

n

uuur uuuuur

∑ OP × OP
i −1

i

i +1

(8c)

* Ta sẽ chứng minh công thức tính diện tích đa giác theo tọa độ các đỉnh.
uuur

Vì điểm Pi có tọa độ tương ứng là (x i; yi) nên các vecto OPi có tọa độ tương
ứng là (xi ; yi), dựa vào công thức tích chéo, ta có
S=

1

- Nếu không thì:
+) Từ A xác định một tia gốc A không đi qua đỉnh nào của đa giác, ta gọi
tia này là tia AB. Có nhiều cách chọn tia này, ví dụ như chọn ngẫu nhiên n+1
tia đôi một khác nhau, khi đó chắc chắn sẽ có một tia không đi qua đỉnh nào
của đa giác. Tuy nhiên, trên thực tế, phương pháp hiệu quả hơn được áp dụng

14


là: sinh ngẫu nhiên một tia, nếu tia đó đi qua một đỉnh của đa giác thì sinh
ngẫu nhiên một tia khác và thử lại.
+) Nếu tia AB cắt cạnh đa giác một số lẻ lần thì điểm A nằm trong đa giác,
ngược lại thì điểm A nằm ngoài đa giác.
C. Bài tập
Bài 1: Triangle and point
Cho tam giác ABC và 1 điểm M không nằm trên cạnh của tam giác.
Yêu cầu: Hãy viết chương trình tính số lớn nhất R sao cho vòng tròn tâm M,
bán kính R không cắt bất cứ cạnh nào và không chứa tam giác ABC.
Input: Ghi trong file TRIANGLE.INP
- Dòng đầu tiên ghi 6 số thực là toạ độ ba đỉnh của tam giác Ax Ay Bx
By Cx Cy
- Dòng thứ hai ghi toạ độ điểm M : Mx

My

Các số thực được viết với 1 chữ số thập phân, cách nhau bởi 1 dấu cách
Output: ghi ra file TRIANGLE.OUT gồm 1 số duy nhất R làm tròn đến 1
chữ số sau dấu phảy.
Ví dụ
TRIANGLE.OUT

M3

kéo dài và tia vuông góc với BC tại B:
thì R = M1B

- Ở vị trí M2 bị giới hạn bởi hai tia tia thứ nhất vuông góc với BC tại B và tia
thứ hai vuông góc với BC tại C: thì R = d(M2, BC)
- Ở vị trí M3 bị giới hạn bởi cạnh AC kéo dài và tia vuông góc với BC tại C:
thì R = M3C
Tương tự như vậy với hai trường hợp còn lại.
Cài đặt
Uses

math;

const

finp='triangle.inp';
fout='triangle.out';

var

fi,fo:text;
n,i,test:longint;
xa,ya,xb,yb,xc,yc,xm,ym,r:extended;

function kc(x1,y1,x2,y2:extended):extended;
begin
exit(sqrt(sqr(x2-x1)+sqr(y2-y1)));
end;


a1,a2,b1,b2,c1,c2,x3,y3,a,b,c:extended;

begin
a1:=x2-x1;b1:=y2-y1;c1:=a1*xm+b1*ym;
a2:=b1;b2:=-a1;c2:=a2*x1+b2*y1;
y3:=(c1*a2-c2*a1)/(b1*a2-b2*a1);
x3:=(c1-b1*y3)/a1;
a:=kc(x3,y3,xm,ym);
b:=kc(x1,y1,xm,ym);
c:=kc(x2,y2,xm,ym);
17


if kc(x1,y1,x3,y3)+kc(x2,y2,x3,y3)kc(x1,y1,x2,y2)

Khu vườn của Phú Ông
Yêu cầu: Cho d là độ dài sợi dây và tọa độ tâm của n cây, các cây có bán
kính r. Hãy giúp Phú Ông tìm cách chọn để giữ lại nhiều cây nhất.
Dữ liệu: Vào từ thiết bị vào chuẩn: Dòng đầu tiên ghi số nguyên dương K là
số lượng bộ dữ liệu. Tiếp đến là K nhóm dòng, mỗi nhóm tương ứng với một
bộ dữ liệu có cấu trúc như sau:
- Dòng thứ nhất ghi ba số nguyên dương d, n và r (d ≤ 109 ; r ≤ 100)
- n dòng tiếp theo, dòng thứ i chứa hai số nguyên xi, yi (|xi|, |yi| ≤ 1000).
19


Dữ liệu đảm bảo các hình tròn không giao nhau. Các số trên cùng một dòng
được ghi cách nhau ít nhất một dấu cách.
Kết quả: Ghi ra thiết bị ra chuẩn gồm K dòng, mỗi dòng ghi một số nguyên là
số lượng cây mà Phú Ông có thể giữ lại được ứng với bộ dữ liệu trong file dữ
liệu vào.
Sub 1: n
tree, p

:array[1..MAX]of Point;

d

:array[1..MAX]of longint;

nTree, nTest, n :longint;
r,L

:extended;

best

:longint;

f, g

:text;

function Dist(p1, p2: Point): extended;
begin
Dist := Sqrt(Sqr(p1.x - p2.x) + Sqr(p1.y - p2.y));
end;
procedure Extract(p1,p2: Point;var a,b,c: extended);
begin
a := p1.y - p2.y;
b := p2.x - p1.x;
with p1 do c := -(a*x + b*y);

end;
end;
end;
exit(true);
end;
procedure sol;
var i,j,k :longint;
sum

:extended;

begin
n:=0;
for k:=1 to nTree do
if d[k] = 1 then begin
inc(n);
22


p[n]:=tree[k];
end;
k:=0;
sum:=0;
for i:=1 to n do
for j:=i+1 to n do
if check(p[i],p[j]) then begin
inc(k);
sum:=sum + Dist(p[i],p[j]);
end;
if k = 1 then sum:=sum * 2;


read(f,tree[i].x,


end;
end;
BEGIN
assign(f,fi); reset(f);
assign(g,fo); rewrite(g);
readln(f,nTest);
while nTest > 0 do begin
dec(nTest);
readFile;
best:=0;
bk(1);
writeln(g,best);
end;
close(f);
close(g);
END.
III. HIỆU QUẢ DO SÁNG KIẾN ĐEM LẠI
1. Hiệu quả kinh tế
2. Hiệu quả về mặt xã hội
Sau khi dạy cho học sinh khối chuyên tin về phương pháp ứng dụng
vecto vào giải quyết một số bài toán hinh học trong tin học, tôi thấy các em đã
có nhiều chuyển biến về phương pháp giải các bài toán về hình học trong tin
học. Đặc biệt là các em đã có sự thay đổi nhiều về cách thiết kế thuật toán cho
các bài toán hình học đặc biệt là đã biết dùng tìm cách giải tốt trong toán học
để thiết kế thuật toán và cài đặt chương trình để có hiệu quả cao. Chính vì vậy,
trong các kỳ thi học sinh giỏi tỉnh, vùng duyên hải đồng bằng Bắc Bộ, Quốc