SKKN Những vấn đề cần lưu ý khi giải một số bài toán hình học trong lập trình

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 sinh, bạn bè đồng nghiệp và những người yêu lập trình.
2. MỤC ĐÍCH CỦA ĐỀ TÀI
Đề tài có mục đích đưa ra các cấu trúc dữ liệu phù hợp để biểu diễn các yếu tố hình học, xây dựng các công thức (Thuật toán) giải các bài toán hình học cơ bản. Ngoài ra trong phần phụ lục của đề tài còn đưa ra một số bài toán hình học thường gặp và thuật toán giải để bạn đọc tham khảo.
3. ĐỐI TƯỢNG NGHIÊN CỨU CỦA ĐỀ TÀI
 Các cấu trúc dữ liệu để biểu diễn các đối tượng hình học, các thuật toán giải các bài toán hình học cơ bản, một số bài toán hình học thường gặp và thuật toán giải chúng.
3. PHƯƠNG PHÁP NGHIÊN CỨU CỦA ĐỀ TÀI
- Xây dựng cơ sở lý thuyết. 
- Điều tra khảo sát thực tế, đối sánh.
PHẦN 2. NỘI DUNG
I – BIỂU DIỄN CÁC ĐỐI TƯỢNG CƠ BẢN CỦA HÌNH HỌC
I.1. Biểu diễn điểm, đoạn thẳng và đường thẳng
Như chúng ta đã biết, các khái niệm: điểm, đoạn thẳng, đường thẳng là những đối tường cơ bản nhất trong hình học nói chung. Để biểu diễn các đối tượng nói trên trong tin học có nhiều cách khác nhau, tuy nhiên ta có thể sử dụng cách biểu diễn bằng các cấu trúc dữ liệu như sau:
Type
// Điểm 
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. 
Đ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 đó.
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.
+ Kiểu số nguyên:
Tên kiểu
Phạm vi
Dung lượng
 Shortint
-128 → 127
1 byte
 Byte
0 → 255
1 byte
 Integer
-32768 → 32767
2 byte
 Word
0 → 65535
2 byte
 LongInt
-2147483648 → 2147483647
4 byte
+ 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
5.0×10-324 → 1.7×10+308
8 byte
Extended
3.4×10-4932 → 1.1×10+4932
10 byte
Trong khi sử dụng kiểu dữ liệu kiểu số thực, mặc dù chỉ khi ta dùng Double hoặc Extended ta mới phải khai báo biên dịch ở chế độ {$N+}, nhưng ta nên lúc nào cũng làm như vậy. Vì khi đó máy tính sẽ dùng bộ đồng xử lý toán học, các phép toán với số thực sẽ thực hiện nhanh chẳng kém gì so với số nguyên (thậm chí còn nhanh hơn nếu ta dùng kiểu số thực Double).
II. THUẬT TOÁN GIẢI MỘT SỐ BÀI TOÁN HÌNH HỌC CƠ BẢN
II.1. Tính toán hoặc so sánh độ dài của đoạn thẳng, chu vi, diện tích các hình
Đối với đoạn thẳng, việc tính toán hay so sánh độ dài của đoạn thẳng này với đoạn thẳng khác dựa trên tọa độ sẽ không thể thực hiện được một cách chính xác nếu như trong công thức có xuất hiện dấu căn. Thay vào đó ta phải viết biến đổi công thức toán học thành một dạng khác sao cho không còn xuất hiện dấu căn thức.
- Để so sánh độ dài của hai đoạn thẳng, đoạn thẳng thứ nhất nối giữa hai điểm M1(x1; y1) , M2(x2;y2) và đoạn thẳng thứ hai nối giữa hai điểm M3(x3; y3), M4(x4;y4).
Function EQA (x,y : doan) : boolean;
Begin
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 đoạn x}
then exit(False)
End;
Ở đây chúng ta cần lưu ý là ta đã so sánh bình phương độ dài hai đoạn thẳng, điều này giúp giảm chi phí tính toán đồng thời không phải so sánh 2 số thực nếu tọa độ nguyên.
- Điều kiện 3 điểm A(XA,YA), B(XB,YB), C(XC,YC) thẳng hàng: 
 (XA-XB)*(YA-YC) = (XA-XC)(YA-YB).
II.2 Vị trí tương đối giữa ba điểm liên tiếp A, B, C:
Có 3 khả năng xảy ra:
Nếu k = 0 thì ba điểm A, B, C thẳng hàng, k 0 thì ta có rẽ trái tại B.
Khi lập trình ta có thể dùng hàm như sau:
Function CCW (A,B,C : point) : integer;
Begin
If = 0 then exit(0);
If < 0 then exit(1)
Else exit(-1);
End;
II.3. Phương trình đường thẳng
Phương trình đường thẳng đi qua hai điểm phân biệt P1, P2 có dạng:
f(x,y) = (x- P1.x)*(P2.y – P1.y) - (y – P1.y)*(P2.x – P1.x) = 0.
Viết dưới dạng tổng quát : f(x,y) = Ax + By + C = 0 như sau:
f(x,y)=(P2.y – P1.y) x +(P1.x – P2.x) y +((P2.x – P1.x)*P1.y - (P2.y – P1.y)* P1.x)=0Ö f(x,y)=(P2.y – P1.y) x +(P1.x – P2.x) y +P2.x*P1.y - P2.y * P1.x=0.
Ở đây chúng ta không nên sử dụng phương trình đường thẳng dạng y=ax+b vì nếu p1p 2 vuông góc với trục ox thì sẽ bị sai.
Để tính giá trị của hàm f(x,y) đi qua hai điểm p1; p2 tại một điểm p3 ta có thể sử dụng đoạn chương trình:
Function fx (p1,p2,p3 : point) : real;
Begin
exit(p3.x*(p2.y – p1.y) + p3.y*(p1.x – p2.x) + ( p2.x*p1.y-p1.x*p2.y));
End;
II.4. Vị trí tương đối giữa điểm và đường thẳng
Cho 3 điểm P1, P2, M, Vị trí tương đối giữa M và so với vector , xác định như sau:
VT := (p2.x-p1.x)(M.y-p1.y)-(p2.y-p1.y)(M.x-p1.x);
- Nếu VT>0 thì M bên trái véctơ 
- Nếu VT<0 thì M bên phải véctơ 
- Nếu VT=0 thì M nằm trên đường thẳng chứa véctơ 
Function PoInLn (p1,p2,M : point) : integer;
Var temp : longint;
Begin
Temp:=(p2.x-p1.x)*(M.y-p1.y)-(p2.y-p1.y)*(M.x-p1.x);
 If Temp = 0 then exit(0);
If Temp > 0 then exit(1) Else exit(-1);
End; { hàm = 1 thì M bên trái , hàm = -1 thì M bên phải}
II.5. Xác định điểm M có thuộc đoạn thẳng P1P2
M thỏa 2 điều kiện sau:
- M nằm trên đường thẳng p1p2
- Tọa độ M thỏa : (M.x>=min(p1.x,p2.x)) and (M.x=min(p1.y,p2.y)) and (M.y<=max(p1.y,p2.y)))
Function PoInLi (p1,p2,M : point) : boolean;
Var temp : longint;
Begin
 Temp:=PoInln(p1, p2,M);
 Exit((Temp=0) and (M.x>=min(p1.x,p2.x)) and 
 (M.x<=max(p1.x,p2.x)) 
 and (M.y>=min(p1.y,p2.y)) and (M.y<=max(p1.y,p2.y))) ;
End;
II.6. Xác định điểm M có thuộc tia AB
Điểm M thuộc tia AB nếu M thuộc đường thẳng AB và với k ≥0:
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
Function PinRay (p1,p2,M : point) : boolean;
Var temp : longint;
Begin
Temp:=PoInln(p1, p2,M);
 Exit((Temp=0) and ((M.x-A.x)*( B.x-A.x)>=0) and 
((M.y-A.y)*( B.y-A.y)>=0));
End;
II.7. Xác định vị trí tương đối giữa 2 điểm M1,M2 so với đường thẳng p1p2
Function Po2PoLi (p1,p2,M1,M2 : point) : boolean;
Var temp1, Temp2 : longint;
Begin
Temp1:= PoInLi (p1,p2,M1 : point);
 Temp2:= PoInLi (p1,p2,M2 : point) ;
Exit(Temp1 *Temp2 >= 0);
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:
- Tính hệ số A1, B1, C1 của đường thẳng AB.
- Tính hệ số A2, B2, C2 của đường thẳng CD.
- Tính ; ;
- Nếu D0 thì cắt nhau
- Ngược lại
 - 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;
Var a1, b1, c1, a2, b2, c2:real; d, dx, dy: real;
Begin
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.
 d:=a1*b2- a2*b1;
 dx:= c2*b1- c1*b2;
 dy:= a1*c2- a2*c1;
 If (d = 0) then
 If (dx= 0) and (dy= 0) then exit(0) // trùng nhau
 Else exit(-1) // song song
Else // d0
Begin
 I.x:=dx/d; I.y:=dy/d; exit(1);
End;
End;
II.8. Xác định 2 đoạn thẳng có giao nhau hay không
 Hai đoạn thẳng giao nhau nếu thỏa điều kiện:
- Hai đường thẳng qua 2 điểm đó phải cắt nhau tại một điểm I
- Và I thuộc 2 đoạn thẳng
Cần lưu ý điều kiện thứ hai, có nhiều học sinh hay bỏ sót điều kiện này.
Function Intersect1(A,B,C,D: Point; var I:Point): boolean;
Begin
Exit((Pos2Li(I,A,B,C,D)=1) and PoInLi(I,A,B) and PoInLi(I,C,D);
End;
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.
1.2. Đa giác
Một đa giác là một đường gấp khúc khép kín tức điểm Ak trùng với điểm A1.
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
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
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ở:
2.1. Tính diện tích một đa giác
 // Công thức diện tích kiểu tích phân.
Function Area(P:polygon;n:longint):int64;
Var i:longint; S:real;
Begin
S:=0;
 For i:=1 to n do S:= S+(P[i+1].x-P[i].x)*(P[i+1].y+P[i].y)/2;
Exit(abs(S));
End;
Ở đâ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:
Function Convex (P:polygon;n:longint):boolean;
Var i,j,l,k:longint;
Begin
 For i:=1 to n do
 Begin
 l:=i+1; if l=n+1 then l:=1; // đỉnh kế với i
 k:=i+2; if l=n+1 then k:=1; // đỉnh xét cùng phía
 for j:=1 to n do // vét tất cả các đỉnh // 
 if (ji) and (jk) and
 (jl) and (not Pos2PoLi(P[i],P[l],P[k],P[j]))
 then exit(false);
End;
exit(true);
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.
Function Inside (P:polygon;n:longint;M:point):boolean;
Var i:longint; VT, VT1:integer;
Begin
 If PoInLi(P[1], P[2],M) then exit(true);
 VT:=PosPoVec(P[1],P[2],M);
 For i:=2 to n do
 Begin
 If PoInLi(P[i], P[i+1],M) then exit(true);
 VT1:=PosPoVec(P[i],P[i+1],M);
 If (VT* VT1)<0 then exit(false);
 end;
 exit(true);
End;
+ Đối với đa giác bất kỳ:
- 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:
Function Inside (P:polygon;n:longint;M:point):boolean;
Var I,count:longint; I,N point; xmax:real;
Begin
 P[n+2]:=P[2]; // phần tử cầm canh. Ta có sẵn P[0]:=P[n], P[n+1]:=P[1]
 Count:=0; // đếm số giao điểm
 xmax:=findxmax(P); // tìm hoành độ lớn nhất của đa giác
 N.x:=xmax+1; // điểm N
 N.y:=M.y;
 For i:=1 to n do
 Begin
 If PoInLi(P[i],P[i+1],M) then exit(true); // M thuộc cạnh
 If not PoInLi(M,N,P[i]) then
 Begin
 If (not PoInLi(M,N, P[i+1])) and (Intersect(M,N,P[i],P[i+1],I))
 then inc(count) // trường hợp 3
 Else if not PoInLi(M,N, P[i+2]) and (not Pos2PoLi(M,N,P[i],P[i+2]))
 then inc(count); // trường hợp 1
 End;
 Else if PoInLi(M,N, P[i+1]) and (not Pos2PoLi(M,N,P[i-1],P[i+2]))
 Then inc(count) // trường hợp 2
 End;
 If (count mod 2 0) then exit(true);
 Exit(false);
End;
2.4. Tìm bao lồi có chu vi nhỏ nhất
Bài toán: Cho tập M gồm N điểm phân biệt.Tìm tập con H của M sao cho H là tập các đỉnh của đa giác lồi chứa tất cả các điểm của M trong miền đa giác đó. .
 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 đượcQuá 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}
 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;
 Angle := t;
end;
Sau đây là thủ tục tìm bao lồi theo thuật toán bọc gói.
procedure Wrap;
var
 i, li: Integer;
 min, tmp: Real;
 t: Point;
begin
 t := p[1];
 li := 1;
 for i := 2 to n do
 if (p[i].y < t.y)or(p[i].y = t.y)and(p[i].x < t.x) then
 begin
	 t := p[i];
	 li := i;
 end;
 p[n + 1] := t; {để phát hiện thời điểm kết thúc}
 m := 0; {m sẽ là số điểm trên bao}
 repeat
 Inc(m);
 p[li] := p[m];
 p[m] := t;
 min := max; 
 for i := m + 1 to n + 1 do
 begin
	 tmp := Angle(p[i], p[m]);
	 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(N2). 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ột điểm là khúc rẽ trái, vì tất cả các điểm từ đó lùi về 1 chắc chắn sẽ thuộc bao.
	.
Cài đặt không phải là một vấn đề khó nhưng phải cảnh giác với sai số và các điểm thẳng hàng.
Việc xây dựng đường khép kín đơn không thực sự phải dùng hàm Angle vì dễ gây sai số và chi phí hơi lớn. Vì tất cả các tia tạo bởi điểm chốt và một điểm bất kỳ đều trong góc phần tư I và II nên ta có thể dùng hàm Lower sau để làm phép so sánh cho việc sắp xếp.
function Lower(p1, p2: Point): Boolean;
var
 a1, b1, a2, b2: Real;
begin
 a1 := p1.x – p[1].x;
 b1 := p1.y – p[1].y;
 a2 := p2.x – p[1].x;
 b2 := p2.y – p[1].y;
 Lower := a1*b2 > a2*b1;
end;
Thực chất ta đã so sánh hai giá trị a1/b1 và a2/b2, tức là cotg của hai góc. Nhưng ta không làm như vậy vì phải xét b1, b2 liệu có bằng 0 hay không.
Sau đây là đoạn chương trình miêu tả phương pháp quét Graham. Ta coi mọi công việc khởi tạo đã xong xuôi. Hàm CCW đã nói tới ở phần trước.
procedure GrahamScan;
var
 i: Integer;
begin
 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;
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.
PHẦN 3. KẾT LUẬN
Trong khuôn khổ một đề tài sáng kiến kinh nghiệm nên đề tài mới chỉ đề xuất cách sử dụng một số cấu trúc dữ liệu dể biểu diễn các yếu tố hình học, đưa ra thuật toán giải một số bài toán hình học cơ bản (trong mục I PHẦN 2). Trong mục II đề tài trình bày một số bài toán hình học cơ bản, trong đó các bài đều có nêu thuật toán giải, một số bài có chương trình minh họa kèm theo, một số bài để các em học sinh luyện tập rèn luyện kỹ năng lập trình. Mục III trình bày thuật toán giải một số bài toán cơ bản về đa giác Việc lập trình giải các bài toán hình học thường là vấn đề đòi hỏi học sinh phải chịu khó, cẩn thận và nắm được những kiến thức cơ bản về hình học và thường là khó đối với học sinh. Tuy nhiên nếu thầy cô có phương pháp tốt để học sinh tích cực, chủ động lĩnh hội được các kiến thức, chủ động rèn luyện kỹ năng kỹ xảo thì việc giải các bài toán này sẽ trở nên dễ dàng hơn đối với học sinh. 
Qua quá trình giảng dạy môn Tin học cho các đối tượng học sinh bậc THPT cả chuyên và không chuyên, khi dạy về phần lập trình giải các bài toán hình học tôi đều cung cấp cho các em các kiến thức như đã trình bày trong đề tài (mức độ có khác nhau tùy từng đối tượng). Qua theo dõi đánh giá thì đa số học sinh đều tiếp thu được và sau khi đã nắm được các kiến thức cơ bản như trong đề tài thì khi gặp các bài toán hình học khác các em giải quyết các bài toán đó hiệu quả hơn rất nhiều so với trước đó.
Vì điều kiện hạn chế về thời gian và khuôn khổ của đề tài nên các bài tập ví dụ chưa nhiều và cũng chưa bao quát hết các dạng, mặt khác đề tài cũng không tránh khỏi hạn chế, thiếu sót nhất định. Tôi hy vọng nhận được những góp ý đóng góp của bạn bè đồng nghiệp để đề tài được hoàn thiện hơn, góp phần nhỏ cho công tác giảng dạy bồi dưỡng học sinh . 
Tôi xin chân thành cảm ơn!
XÁC NHẬN CỦA THỦ TRƯỞNG ĐƠN VỊ
Thanh Hóa, ngày 15 tháng 5 năm 2017
Tôi xin cam đoan đây là SKKN của mình viết, không sao chép nội dung của người khác.
Nghiêm Q