Sáng kiến kinh nghiệm Tích hợp liên môn chủ đề hình học phẳng trong Tin học

tor B) 
{ 
 return A.x * B.y - A.y * B.x; 
} 
Point M , N , A , B , C , D , a[Array_Size]; 
int n; 
Path Get_Path(Point A , Point B) // Tra ve phuong trinh duong thang AB 
{ 
 Vector U = {B.x - A.x , B.y - A.y}; 
 double a = -U.y , b = U.x , c = - (a * A.x + b * A.y); 
 return {a , b , c}; 
} 
Point Intersect(Path X , Path Y) // Tra ve giao diem 2 duong thang X va Y 
27 
{ 
 double a1 = X.a , b1 = X.b , c1 = -X.c; 
 double a2 = Y.a , b2 = Y.b , c2 = -Y.c; 
 double D = a1 * b2 - a2 * b1; 
 double Dx = c1 * b2 - c2 * b1; 
 double Dy = a1 * c2 - a2 * c1; 
 if(D == 0) 
 { 
 if(Dx == Dy && Dx == 0) return {-inf , 0}; 
 else return {inf , 0}; 
 } 
 else return {Dx * 1.0 / D , Dy * 1.0 / D}; 
} 
double F(Point M , Point A , Point B) // Thay M vao phuong trinh duong thang AB 
{ 
 Path D = Get_Path(A , B); // Phuong trinh duong thang AB 
 return M.x * D.a + M.y * D.b + D.c; 
} 
bool Kiem_Tra_Diem_Thuoc_Duong_Thang(Point M , Point A , Point B) 
{ 
 if(F(M , A , B) == 0) return true; 
 return false; 
} 
bool Kiem_Tra_Diem_Thuoc_Doan_Thang(Point M , Point A , Point B) 
{ 
 if(F(M , A , B) == 0 && min(A.x , B.x) <= M.x && M.x <= max(A.x , B.x) 
&& min(A.y , B.y) <= M.y && M.y <= max(A.y , B.y)) return true; 
 return false; 
} 
28 
bool Kiem_Tra_Diem_Thuoc_Tia(Point M , Point A , Point B) 
{ 
 if(F(M , A , B) == 0 && (M.x - A.x) * (B.x - A.x) >= 0 && (M.y - A.y) * (B.y 
- A.y) >= 0) return true; 
 return false; 
} 
bool Kiem_Tra_Vi_Tri_2_Diem(Point M , Point N , Point A , Point B) 
{ 
 if(F(M , A , B) * F(N , A , B) < 0) return true; 
 return false; 
} 
void Input() 
{ 
 cin >> M.x >> M.y; 
 cin >> N.x >> N.y; 
 cin >> A.x >> A.y; 
 cin >> B.x >> B.y; 
 cin >> C.x >> C.y; 
 cin >> D.x >> D.y; 
 cin >> n; 
 for(int i = 0 ; i > a[i].x >> a[i].y; 
 a[n] = a[0]; 
 cout << fixed << setprecision(3); 
} 
namespace Tim_Giao_Diem 
{ 
 void Solve() 
 { 
 Point M = Intersect(Get_Path(A , B) , Get_Path(C , D)); // Giao diem 2 
duong thang AB va CD 
29 
 // Tim giao diem 2 duong thang AB va CD 
 if(M.x == inf) cout << "2 duong thang song song\n"; 
 else 
 { 
 if(M.x == -inf) cout << "2 duong thang trung nhau\n"; 
 else cout << "Giao diem la: (" << M.x << ',' << M.y << ")\n"; 
 } 
 // Tim giao diem 2 doan thang AB va CD 
 if(M.x == inf) cout << "2 doan thang khong cat nhau\n"; 
 else 
 { 
 if(M.x == -inf) cout << "2 doan thang co vo so giao diem\n"; 
 else 
 { 
 if (Kiem_Tra_Diem_Thuoc_Doan_Thang(M , A , B) && 
Kiem_Tra_Diem_Thuoc_Doan_Thang(M , C , D)) cout << "Giao diem la: (" << M.x 
<< ',' << M.y << ")\n"; 
 else cout << "2 doan thang khong cat nhau\n"; 
 } 
 } 
 cout << '\n'; 
 } 
} 
#undef int 
int main() 
{ 
 // if(fopen("trash.inp" , "r")) 
 // freopen("trash.inp" , "r" , stdin) , freopen("trash.out" , "w" , stdout); 
30 
 ios::sync_with_stdio(0); 
 cin.tie(0); 
 cout.tie(0); 
 Input(); 
 Tim_Giao_Diem::Solve(); 
} 
2.2.1.5. Vi trí của điểm so với đa giác: 
Bài toán 7. 
Cho đa giác lồi gồm N đỉnh d[1],d[2],...,d[n] và điểm M. Hãy xác định vị trí 
tương đối của M với miền trong của đa giác (nghĩa là xét điểm M thuộc hay không 
thuộc miền đa giác). 
Hướng dẫn: 
Cách 1. 
Nối lần lượt các đường thẳng từ điểm đó đến các đỉnh của đa giác. Thực hiện 
cộng tất cả các số đo góc của góc tạo bởi 2 đỉnh liền kề với điểm đó theo thứ tự các 
đỉnh. Nếu tổng này bằng 360 độ thì điểm đó nằm trong đa giác. 
Điểm P nằm trong đa giác ABCDEF, thỏa điều kiện trên. 
Cách 2. 
Hiển nhiên là nếu M thuộc một cạnh thì M thuộc miền đa giác. 
Ngược lại: Kẻ đoạn thẳng MN song song trục hoành sao cho hoành độ của N 
lớn hơn max của các hoành độ đỉnh đa giác. Xét giao các cạnh của đa giác với đoạn 
31 
thẳng MN. Số giao điểm là lẻ thì M trong đa giác, là chẵn thì M ngoài đa giác. Xét 
cạnh (d[i], d[i+1]) có những trường hợp sau đây được coi như tăng thêm 1 giao điểm: 
Đỉnh d[i] không thuộc đoạn thẳng MN, đỉnh d[i+1] nằm trên đoạn thẳng MN, 
hai đỉnh d[i] và d[i+2] khác phía nhau so với đường thẳng MN. 
Đỉnh d[i-1], d[i+2] ngoài đoạn thẳng MN, hai đỉnh d[i] và d[i+1] thuộc đoạn 
thẳng MN, d[i-1] và d[i+2] khác phía nhau so với đường thẳng MN. 
Đỉnh d[i] và d[i+1] không thuộc MN và cạnh (d[i], d[i+1]) cắt đoạn thẳng MN. 
2.2.1.6. Code chương trình vị trí của điểm so với đa giác (cách 1): 
#defind PI 3.14159265359 
#include 
#include 
#include 
using namespace std; 
class point{ 
private: 
 float x,y; 
public: 
 void setPoint(float a,float b){ 
 x = a;y = b; 
 }; 
 friend point setVector(point a,point b){ 
 point c; 
 c.x = b.x-a.x; 
 c.y = b.y-a.y; 
 return c; 
 }; 
 friend float calculateAngle(point vectora,point vectorb){ 
 float t = (vectora.x*vectorb.x + vectora.y*vectorb.y); 
 float m; 
 m = sqrt(pow(vectora.x,2)+pow(vectora.y,2))*sqrt(pow(vectorb.x,2)+pow(vectorb.y,2)); 
 return acos(t/m); 
32 
 }; 
}; 
class polygon{ 
private: 
 point *p; 
 int n; 
public: 
 polygon(int m){ 
 n = m; 
 p = new point[m]; 
 }; 
 void setPolygon(){ 
 float a,b; 
 for(int i=0;i<n;i++){ 
 cout<<"x("<<i+1<<") = "; 
 cin>>a; 
 cout<<"y("<<i+1<<") = "; 
 cin>>b; 
 p[i].setPoint(a,b); 
 } 
 }; 
 void testInPolygon(point P){ 
 point vectora,vectorb; 
 float sum = 0; 
 for(int i=0;i<n-1;i++){ 
 vectora = setVector(p[i],P); 
 vectorb = setVector(p[i+1],P); 
 sum = sum+calculateAngle(vectora,vectorb); 
 } 
 vectora = setVector(p[n-1],P); 
 vectorb = setVector(p[0],P); 
 sum = sum+calculateAngle(vectora,vectorb); 
 if(abs(sum-2*PI)<=0.01) 
 cout<<"diem nam trong hinh"; 
 else 
 cout<<"diem nam ngoai hinh"; 
 }; 
 ~polygon(){ 
33 
 delete []p; 
 }; 
}; 
void main(){ 
 int m; 
 float a,b; 
 cout<<"nhap so dinh cua da giac: "; 
 cin>>m; 
 polygon A(m); 
 A.setPolygon(); 
 point P; 
 cout<<"nhap diem can xet: "; 
 cout<<"x = "; 
 cin>>a; 
 cout<<"y = "; 
 cin>>b; 
 P.setPoint(a,b); 
 A.testInPolygon(P); 
} 
2.2.1.7. Đa giác lồi. 
Bài toán 8. 
Kiểm tra một đa giác N đỉnh có là đa giác lồi hay không? 
 Hướng dẫn: 
Đa giác là lồi nếu với mọi cạnh nối đỉnh i (1iN) với đỉnh i+1 (đỉnh N+1 coi 
như đỉnh 1) thì mọi đỉnh j (1jN) và đỉnh i+2 phải luôn luôn cùng phía so với 
đường thẳng chứa cạnh (i, i+1). 
2.2.1.8. Đoạn code chương trình đa giác lồi. 
bool dg_loi() 
{ 
int i, j, k, l; 
for (i=1; i<=n; i++) 
 { 
 k=i+2; 
 l=i+1; 
34 
 if (k==n+1) k=1; 
 if (l= n+1) l=1; 
 for (j=1; j<=n; j++) 
 if ((ij) && (! cungfia(x[i],x[l],x[j],x[k],y[i],y[l],y[j],y[k])) 
 return false; 
 } 
return true; 
} 
 2.2.2. Bài tập vận dụng. 
 Có hướng dẫn, code và test kèm theo giúp học sinh tự làm bài, tham khảo 
code mẫu và tự chấm bài theo test. 
Bài tập 1. ĐA GIÁC. 
Xét một đa giác lồi có N đỉnh, không có ba đường chéo nào đồng quy tại một 
điểm duy nhất. Tìm số giao điểm giữa các cặp đường chéo của hình đa giác. 
Ví dụ cho hình một đa giác có 6 đỉnh. Ta có số giao điểm như hình vẽ. 
Lưu ý: một đa giác là lồi nếu tất cả các góc bên trong của nó nhỏ hơn 180 độ. 
Dữ liệu vào từ file DAGIAC.inp: Chỉ một số N là số dỉnh của đa giác (3<N<100). 
Kết quả ghi ra file DAGIAC.out: Chỉ 1 số duy nhất là số giao điểm tìm được. 
Vi dụ: 
DAGIAC.inp DAGIAC.out DAGIAC.inp DAGIAC.out 
3 0 6 15 
Hướng dẫn: 
35 
Hãy tưởng tượng rằng các đỉnh của đa giác được đánh dấu từ 0 đến N-1 liên 
tiếp. Xét một đường chéo từ đỉnh 0 đến đỉnh i nào đó. Các đỉnh từ 1 đến i-1 nằm ở 
một phía của đường chéo, các đỉnh từ i + 1 đến N-1 ở phía bên kia. Đường chéo chỉ 
cắt những đường chéo có một đỉnh ở bên này và đỉnh ở bên kia. Do đó có (i-1) * (N-
1-i) đường chéo cắt nó. Đếm tất cả các đường chéo có một đỉnh là đỉnh 0 và nhân số 
đường chéo với n ( có thể gắn nhãn bất kỳ đỉnh 0 nào và sẽ nhận được kết quả tương 
tự). Ta đã đếm mỗi giao điểm trên một đường chéo hai lần (một lần tính từ mỗi đỉnh 
trên một đường chéo duy nhất) và mỗi giao điểm tổng cộng là bốn lần (vì nó nằm trên 
hai đường chéo). Do đó, ta chia kết quả cho 4. 
Code chương trình 
#include 
Using namespace std; 
int main() 
{ 
 int rez, i, n; 
 cin>>n; 
 rez = 0; 
 for (i=2; i<n-1; i++) 
 { 
 rez += (i-1)*(n-1-i); 
 } 
 rez *= n; 
 rez /= 4; 
cout<<n; 
 return 0; 
} 
Bài tập 2. TAM GIÁC. 
Một khu đất có N cây táo, An mua một mảnh đất hình tam giác trong khu đất 
đó và anh ấy muốn xác định cây táo nào thuộc trong mảnh đất của anh ấy. 
36 
Cho biết tọa độ của các đỉnh của tam giác tạo thành mảnh đất của An, và tọa độ 
của tất cả các cây táo. Xác định diện tích mảnh đất của An và số cây Táo thuộc về anh 
ấy. Coi những cây táo trên chính ranh giới của mảnh đất của An là của anh ấy. 
Diện tích của một tam giác có các đỉnh (xA, yA), (xB, yB) và (xC, y C) được cho 
bởi công thức sau: 
⌈( − ) + ( − ) + ( − )⌉
2
Dữ liệu vào từ file TAMGIAC.inp. 
 Ba dòng đầu tiên, mỗi dòng chứa 2 số là một tọa độ của đỉnh tam giác. 
 Dòng tiếp theo chứa 1 số N (1<N<100) 
 N dòng tiếp theo mỗi dòng chứa 2 số là tọa độ của 1 cây Táo. 
Tất cả các tọa độ đều là số nguyên dương < 1000. 
Kết quả ghi ra file TAMGIAC.out. 
 Dòng đầu là diện tích mảnh đất của An, lấy đến 1 chữ số sau phần thập phân. 
 Dòng tiếp theo chỉ chứa 1 số là số cây Táo trong mảnh đất của An. 
Ví dụ: 
TAMGIAC.inp TAMGIAC.out TAMGIAC.inp TAMGIAC.out 
1 1 
5 1 
3 3 
4 
3 1 
3 2 
3 3 
3 4 
4.0 
3 
2 6 
5 1 
7 8 
5 
1 4 
3 5 
6 4 
6 5 
 4 7 
15.5 
2 
Hướng dẫn: 
Theo công thức về diện tích tam giác đã cho nên ta chỉ cần tìm cách kiểm tra 
xem một điểm P có nằm trong tam giác ABC hay không. Việc kiểm tra có thể được 
thực hiện theo nhiều cách, một trong số đó chỉ tính diện tích hình tam giác. Chính xác 
37 
hơn, tổng diện tích các tam giác ABP, ACP và BCP bằng diện tích ABC nếu và chỉ P 
nằm trong ABC. 
Code chương trình: 
#include 
struct point { int x, y; }; 
int area( point A, point B, point C ) { 
 int t = A.x*(B.y-C.y) + B.x*(C.y-A.y) + C.x*(A.y-B.y); 
 if( t < 0 ) return -t; else return t; 
} 
int main( void ) { 
 point A, B, C; 
 scanf( "%d%d", &A.x, &A.y ); 
 scanf( "%d%d", &B.x, &B.y ); 
 scanf( "%d%d", &C.x, &C.y ); 
 int n, trees = 0; 
 scanf( "%d", &n ); 
 for( int i = 0; i < n; ++i ) { 
 point P; 
 scanf( "%d%d", &P.x, &P.y ); 
 if( area(A,B,P) + area(A,C,P) + area(B,C,P) == area(A,B,C) ) 
 ++trees; 
 } 
 printf( "%.1lf\n", area(A,B,C) / 2.0 ); 
 printf( "%d\n", trees ); 
 return 0; 
} 
Bài tập 3. DIỆN TÍCH 
38 
Có một hồ bơi là một tam giác vuông cân, có cạnh góc vuông là 250. Hồ bơi được 
gắn một hệ tọa độ (như hình vẽ) và được chia thành hai phần có diện tích bằng nhau bởi 
một đoạn thẳng có cả hai điểm mút nằm trên cạnh của hồ bơi. 
Cho trước một điểm cuối của đoạn đường phân chia, Hãy viết một chương trình tính 
tọa độ của điểm cuối còn lại. 
Dữ liệu vào từ file DIENTICH.inp: Chỉ 1 dòng duy nhất chứa 2 số nguyên là tọa độ 
của điểm đầu mút đã cho, điểm đó sẽ nằm trên cạnh của hồ bơi. 
Kết quả ghi ra file DIENTICH.out: Chỉ 1 dòng duy nhất chứa 2 số là tọa độ của 
điểm mút còn lại tìm được, làm tròn đến 2 chữ số ở phần thập phân. 
Ví dụ: 
DIENTICH.inp DIENTICH.out DIENTICH.inp DIENTICH.out 
0 0 125.00 125.00 230 20 0.00 114.13 
Hướng dẫn: 
Có sáu trường hợp riêng biệt, tùy thuộc vào vị trí của điểm đã cho - thuộc phần 
nào trong số sáu phần được dán nhãn trong hình dưới. Trong mỗi trường hợp này, 
chia đôi tam giác sẽ thu được một tam giác nhỏ hơn. Ta biết đáy hoặc chiều cao của 
tam giác nhỏ hơn này từ tọa độ của điểm đã cho và có thể tính độ dài đoạn còn lại từ 
diện tích đã biết của tam giác. Cuối cùng, từ hai con số này, chúng ta có thể tính toán 
tọa độ điểm mút còn lại. Điều quan trọng cần lưu ý là tất cả các điểm trên cạnh huyền 
đều có x + y = 250. 
39 
Code chương trình: 
#include 
struct pt { 
 double x, y; 
 pt() {} 
 pt( double a, double b ) { x=a; y=b; } 
}; 
pt solve( pt a ) { 
 double p = 250*250/2; 
 if( a.x == 0 ) 
 if( a.y < 125 ) return pt( p/(250-a.y), 250-p/(250-a.y) ); 
 else return pt( p/a.y, 0 ); 
 if( a.y == 0 ) 
 if( a.x < 125 ) return pt( 250-p/(250-a.x), p/(250-a.x) ); 
 else return pt( 0, p/a.x ); 
 if( a.x > 125 ) return pt( 0, 250-p/a.x ); 
40 
 else return pt( 250-p/a.y, 0 ); 
} 
int main(void) { 
 pt a, b; 
 scanf( "%lf%lf", &a.x, &a.y ); 
 b = solve( a ); 
 printf( "%.2lf %.2lf\n", b.x, b.y ); 
 return 0; 
} 
Bài tập 4. GIAO ĐIỂM 
Ở một công viên xa xôi, người ta làm các xà đu để vui chơi. Một xà đu được mô 
tả bằng ba con số: tọa độ x của cột trái L và cột phải R, và chiều cao H tại đó 2 cột 
được kết nối bằng 1 đoạn ngang. Hình ảnh mô tả một xà đu có L = 2, R = 5 và H = 4. 
 Mỗi ngày họ sẽ làm thêm 1 xà đu. Xà đu đầu tiên có chiều cao 1, và mỗi xà đu 
sau cao hơn xà đu trước 1 đơn vị. Khi đoạn ngang của xà đu này giao với đoạn ngang 
của xà đu kia họ sẽ làm một bông hoa nhỏ tại giao điêm (nếu ở đó chưa có bông hoa 
nào). Nếu các đoạn ngang chỉ giao nhau tại điểm mút thì không làm hoa ở đó. Ví dụ 
về hình ảnh của 4 xà đu đầu tiên. 
41 
 Cho biết số ngày làm xà đu và vị trí các xà đu, hãy viết chương trình tính số bông 
hoa mới được tao ra mỗi ngày. 
Dữ liệu vào từ file GIAODIEM.inp: 
 Dòng đầu tiên chứa 1 số nguyên N (1< N < 105), là số xà đu. 
 N dòng tiếp theo, mỗi dòng 2 số nguyên L và R (1< L < R < 105). 
Kết quả ghi ra file GIAODIEM.out: 
 Có N dòng, mỗi dòng là số bông hoa mới tạo ra của ngày đó. 
Ví dụ: 
GIAODIEM.inp GIAODIEM.out GIAODIEM.inp GIAODIEM.out 
4 
1 4 
3 7 
1 6 
2 6 
0 
1 
1 
2 
5 
1 3 
3 5 
3 9 
2 4 
3 8 
0 
0 
0 
3 
2 
Hướng dẫn: 
Mô phỏng bằng một bảng hai chiều có độ phức tạp là O (N2 + N · M), trong đó M 
là tọa độ cực đại. Giải pháp này đạt 30 điểm. Gọi A(x) là số xà đu có thể làm ở tọa độ 
x (nhưng chưa có). Dãy A ban đầu chứa tất cả các số không và những thay đổi khi xà 
đu (L, R) được làm: 
 • Hoa sẽ được tạo ở tọa độ L và R, tổng số A (L) + A (R) của chúng, vì vậy ta 
xuất ra số đó. Sau khi những bông hoa này đã làm, không còn xà đu nào ở tọa độ L và 
R, vì vậy chúng tôi đặt lại A (L) và A (R) về không. 
42 
 • Đoạn ngang [L + 1, R − 1] bây giờ có sẵn để tạo hoa, vì vậy chúng ta tăng A (x) 
lên một cho mỗi tọa độ đó. Việc thực hiện trực tiếp thuật toán trên có độ phức tạp 
O(NM), đạt được 45 điểm. Để đạt được hết test, chúng ta cần một cấu trúc dữ liệu hỗ 
trợ các hoạt động sau: 
• Đặt A (x) = 0; 
• Tăng A (x) lên một cho mỗi x trong [L-1, R + 1]. Một số cấu trúc dữ liệu thực 
hiện điều này là cây IT và cây Fenwick cho O (log N) cho mỗi truy vấn hoặc tách 
chuỗi A thành các khối có kích thước khoảng sqrt (N), cho O (sqrt (N)) cho mỗi truy 
vấn. 
Code chương trình: 
#include 
int N; 
int A[100001]; 
int B[1000]; 
int main( void ) { 
 scanf( "%d", &N ); 
 for( int i = 0; i < N; ++i ) { 
 int L, R; 
 scanf( "%d%d", &L, &R ); 
 printf( "%d\n", A[L]+B[L>>8] + A[R]+B[R>>8] ); 
 A[L] = -B[L>>8]; 
 A[R] = -B[R>>8]; 
 int x = L+1; 
 for( ; x < R && (x&0xFF); ++x ) ++A[x]; 
 for( ; x+256 >8]; 
 for( ; x < R; ++x ) ++A[x]; 
 } 
 return 0; 
} 
Bài toán 5. ĐƯỜNG THẲNG. 
43 
 Cho N đường thẳng, phương trình có dạng Ai x + Bi y + Ci = 0 trong mặt phẳng 
tọa độ. Tính toán số tam giác có các cạnh nằm trên các đường thẳng cho trước. Vì kết 
quả có thể rất lớn, hãy xuất ra kết quả sau khi mod 1000000007. 
Lưu ý: Không có 3 đường thẳng nào đồng quy tại 1 điểm. 
Dữ liệu vào từ file DUONGTHANG.inp: 
 Dòng đầu chứa 1 số nguyên N là số đường thẳng (1< N < 300). 
 N dòng tiếp theo mỗi dòng chứa 3 số nguyên: Ai, Bi, Ci là các hệ số của đường 
thẳng thứ i. (Ai, Bi, Ci < 10
9). 
Kết quả ghi ra file DUONGTHANG.out: Chỉ 1 số duy nhất là số tam giác tìm được. 
Ví dụ: 
DUONGTHANG.inp DUONGTHANG.out DUONGTHANG.inp DUONGTHANG.out 
6 0 1 0 
-5 3 0 
-5 -2 25 
 0 1 -3 
 0 1 -2 
-4 -5 29 
10 5 
-5 3 0 -5 -3 -30 0 1 0 3 
7 35 1 -2 -1 
Hướng dẫn: 
Xét ba đường thẳng khác nhau, ta có thể nhận thấy rằng chúng tạo thành một tam 
giác khi và chỉ khi độ dốc của chúng khác nhau. Các đường thẳng i và j có độ dốc 
khác nhau nếu Ai / Bi khác Aj / Bj (hãy cẩn thận với phép chia cho 0). Điều này dẫn 
đến giải pháp đầu tiên với độ phức tạp của O (N3), bằng cách kiểm tra xem các độ dốc 
có khác nhau đối với mọi bộ ba dòng (i, j, k) hay không. 
44 
Nếu có thể tìm ra có bao nhiêu đường có độ dốc khác với độ dốc của một cặp 
đường nhất định, nhiệm vụ có thể được giải quyết bằng cách cố định tất cả các cặp 
đường (i, j) có độ dốc khác nhau và thêm câu trả lời vào truy vấn dòng i và j. 
Gọi f(x) biểu diễn số đường thẳng có hệ số góc bằng hệ số góc của đường thẳng x. 
Khi đó số đường có hệ số góc khác với hệ số góc của đường thẳng i và j là N - f(i) - 
f(j). Các giá trị của f(x) có thể được xử lý trước theo độ phức tạp của O (N lg N) bằng 
cách sắp xếp đơn giản, và giải thuật của bài có độ phức tạp O (N2). 
Để đạt được 100% số điểm, ta tính hai hàm mới: Maxf(x) và minf(x) cho chúng ta 
biết có bao nhiêu đường có độ dốc lớn hơn hoặc nhỏ hơn độ dốc của đường x. 
Maxf(x) và minf(x) cũng có thể được xử lý trước dễ dàng với độ phức tạp của O 
(NlgN) với sự trợ giúp sắp xếp. Số lượng hình tam giác có đường thẳng i thuộc và có 
kích thước độ dốc ở giữa có thể được tính là Maxf(x)*minf(x). Cuối cùng, ta chỉ cần 
tính tổng các giá trị này cho mỗi i từ 1 đến N. Tổng độ phức tạp là O (N lg N). 
Code chương trình: 
#include 
#include 
using namespace std; 
const int MAXN = 300010; 
const int MOD = 1000000007; 
typedef long long llint; 
int n; 
pair p[MAXN]; 
bool cmp (pair a, pair b) { 
 return (llint)a.first * b.second < (llint)a.second * b.first; 
} 
int main(void) { 
 scanf("%d", &n); 
 for(int i = 0; i < n; ++i) { 
 int a, b; scanf("%d%d%*d", &a, &b); 
 p[i] = make_pair(a, b); 
45 
 } 
 sort(p, p + n, cmp); 
 int l = 0, r = 0; 
 llint ans = 0; 
 for(int i = 0; i < n; ++i) 
 { 
 while(cmp(p[l], p[i])) ++l; 
 while(r < n && !cmp(p[i], p[r])) ++r; 
 ans += (llint)l * (n - r) % MOD; 
 ans %= MOD; 
 } 
 printf("%lld\n", ans); 
 return 0; 
} 
46 
3.Phân tích, đánh giá kết quả. 
Việc ứng dụng đề tài trong dạy và học toán hình học phẳng tạo hứng thú cho học 
sinh và giảm thời gian tính toán kết quả cụ thể cho giáo viên trong việc tính đáp án. 
 Đề tài giúp cho việc bỗi dưỡng HGS đạt hiệu quả tốt hơn, học sinh đã tự tin hơn 
với các bài toán xử lý hình học, các bài toán về diện tích, bao lồi trong các đề thi 
HSG. 
Vì thời gian hoàn thành đề tài có hạn nên chương trình phần mềm Hinhhoc.exe 
chỉ tập trung vào việc đưa ra kết quả bài toán cần tìm, chứ chưa tạo giao diện đẹp cho 
màn hình kết quả. 
Đề tài đã được áp dụng thực hiện tại trường THPT Kim Liên – Nam Đàn và 
trường THPT chuyên Phan Bội Châu và đã thu được kết quả rất tốt. Các em học sinh 
học tập hứng thú và vận dụng tốt với phần kiến thức được áp dụng. 
PHẦN III. KẾT LUẬN. 
Việc dạy học tích hợp liên môn giúp cho quá trình học có ý nghĩa hơn, thiết lập 
mối quan hệ giữa các kiến thức, các môn học. Học sinh thấy được ứng dụng các kiến 
thức học được với thực tế. 
Đề tài áp dụng tốt trong công tác bồi dưỡng HSG, ứng dụng tốt trong việc giải 
các bài toán thực tiễn có yếu tố hình học. 
Có thể mở rộng việc sử dụng ngôn ngữ lập trình để viết các phần mềm về các 
bài toán cơ bản của các chuyên đề khác trong toán học, hay các môn tự nhiên như Lý, 
Hóa, Sinh, sẽ hỗ trợ cho giáo viên và học sinh trong việc tính nhanh các kết quả của 
các bài toán cơ bản cụ thể khi nhập các thông số ban đầu. 
 Vinh ngày 25 tháng 3 năm 2021 
 Người viết: Lê Thị Nhung 
 Lê Thị Mỹ Hạnh