Phương pháp giải toán hình học bằng ngôn ngữ lập trình Pascal

 các điểm có giá trị tuyệt đối không quá 10000)
Chương trình:
VD2. Đường thẳng cắt nhau
Cho n đường thẳng AiBi (1 ≤i ≤n) phân biệt với Ai, Bi là các điểm cho trước. Hãy thông báo ra màn hình các cặp đường thẳng đôi một cắt nhau.
Dữ liệu: Cho trong file DL.INP gồm N dòng (N không biết trước). Dòng thứ i ghi 4 số thực xAi yAi xBi yBi. Các số trên cùng một dòng ghi cách nhau ít nhất một dấu cách.
Ý tưởng:
- Mỗi đường thẳng được đặc trưng bởi 3 thông số a,b,c được xác định:
a:=(y1-y2); b:=(x2-x1) ; c:=x1*y2-x2*y1;
- Hai đường thẳng cắt nhau khi: D:=a1*b2-a2*b1 ? 0;
Chương trình:
VD3. Điểm thuộc đa giác.
Cho đa giác không tự cắt A1A2...AN với các đỉnh Ai(xi,yi) nguyên. Với điểm A(xA,yA) cho trước, hãy xác định xem A có nằm trong đa giác đã cho hay không (Trong trường hợp trên cạnh đa giác xem như nằm trong đa giác)
Dữ liệu: Cho trong tệp Dagiac.inp
+ Dòng đầu là số N
+ N dòng tiếp theo mỗi dòng ghi xi,yi là toạ độ Ai
+ Dòng n+2 ghi 2 số xA và yA
Dữ liệu là các số nguyên.
Kết quả: Đưa ra màn hình thông báo điểm A có nằm trong đa giác hay không
Ý tưởng:
- Lưu toạ độ các đỉnh đa giác vào mảng A
- Kiểm tra xem điểm A có trùng với đỉnh đa giác
- Kiểm tra xem điểm A có nằm trên cạnh đa giác
- Tìm giao điểm nếu có của tia Ax (Ax//Ox và Ax hướng theo phần dương trục hoành) với các cạnh của đa giác. Trường hợp tia Ax chứa đoạn thẳng cạnh đa giác ta xem như tia Ax có 1 điểm chung với cạnh này. Cụ thể:
+ Giả sử điểm A(x0,y0), chọn điểm B(xb,yb) với xb=x0+1,yb=y0
+ Kiểm tra tia AB có cắt đoạn thẳng CD bằng cách:
B1. Tìm giao điểm N của 2 đường thẳng AB và CD
Tính
a1:=yb-ya; b1:=xa-xb; c1:=ya*xb-xa*yb;
a2:=yd-yc; b2:=xc-xd; c2:=yc*xd-xc*yd;
D:=a1*b2-a2*b1; Dx:=c2*b1-c1*b2; Dy:=a2*c1-a1*c2;
Xác định: Nếu D ≠0 thì toạ độ giao điểm là N(Dx/D,Dy/D) B2. Kiểm tra N có thuộc tia AM và đoạn thẳng CD hay không.
- Điểm N thuộc đoạn thẳng CD khi: Min(xC,xD) ≤xN ≤ Max(xC,xD) và Min(yC,yD) ≤ yN ≤ Max(yC,yD)
- Điểm N thuộc tia AB khi  có nghĩa là N phải thoả mãn điều kiện: (xN-xA)(xB-xA) ≥0 và (yN-yA)(yB-yA) ≥0
+ Kiểm tra tia AB chưa cạnh CD hay không bằng cách: (yc=yd)and(yc=yo)
- Đếm số giao điểm, nếu số giao điểm lẻ thì A thuộc đa giác
Chương trình:
VD4. Đếm số điểm có toạ độ nguyên thuộc đa giác
Cho đa giác gồm n đỉnh (x1,y1), (x2,y2), ..., (xn,yn), biết xi và yi(i=1,...,n) là các số nguyên trong đoạn [-106,106]. Các đỉnh được liệt kê theo thứ tự cùng chiều kim đồng hồ.
Viết chương trình tìm số điểm có toạ độ nguyên nằm trong hay trên biên đa giác.
Dữ liệu: Cho trong tệp tin DL.INP.
- Dòng đầu chứa số nguyên duy nhất cho biết số đỉnh.
- Tiếp theo là các dòng, trên mỗi dòng có 2 số nguyên cách nhau một khoảng trắng lần lượt là hoành độ, tung độ các đỉnh đa giác.
Kết quả: Xuất ra màn hình số điểm có toạ độ nguyên nằm trong hay trên biên đa giác
Ý tưởng:
- Tính a,b theo công thức:
- Xác định số điểm có toạ độ nguyên: Sđ=round(abs(a/2)+b/2+1)
Chương trình:
Dạng 2.Tính diện tích đa giác
Phương pháp: Giả sử cho đa giác có n đỉnh và toạ độ các đỉnh lưu vào mảng a. Để tính diện tích đa giác ta làm như sau:
Bước 1. Gắn thêm đỉnh phụ:
a[n+1].x:=a[1].x; a[n+1].y:=a[1].y;
Bước 2. Diện tích đa giác tính theo công thức:
Lưu ý: Có thể áp dụng công thức khác để tính diện tích trong các trường hợp đặc biệt.
- Nếu đa giác là tam giác (n=3) thì diện tích tính theo công thức:
- Nếu đa giác là hình chữ nhật (n=4) có các cạnh là a,b thì diện tích là: S=ab
- Nếu đa giác là hình vuông (n=4) có cạnh là a thì diện tích là: S=a2
- Nếu đa giác là hình tròn có bán kính R thì diện tích là
VD1. Xác định diện tích đa giác
Cho N đa giác lồi A1A2A3...AN-1AN với các đỉnh Ai(xi,yi) có toạ độ nguyên. Hãy tính diện tích đa giác trên.
Dữ liệu: Cho trong file DL.INP gồm 2 dòng
- Dòng 1: Chứa số nguyên dương N
- Dòng 2: Chứa 2xN số nguyên dương x1 y1 x2 y2...xN yN là toạ độ các đỉnh của đa giác. Mỗi số ghi cách nhau một dấu cách.
Kết quả: Xuất ra màn hình diện tích đa giác.
Ý tưởng:
- Lưu toạ độ các đỉnh đa giác vào mảng toado
- Sử dụng công thức tính diện tích đa giác:
VD2. Dãy hình chữ nhật
Trong mặt phẳng toạ độ trực chuẩn, cho N hình chữ nhật có các cạnh song song với trục toạ độ. Mỗi HCN được xác định bởi toạ độ đỉnh dưới bên trái và đỉnh trên bên phải của nó. Hãy đưa ra dãy các hình chữ nhật theo thứ tự tăng dần diện tích .
Dữ liệu: Cho trong file HCN.inp gồm N+1 dòng.
- Dòng 1. Chứa số N
-Dòng i+1 (1 ≤i ≤N): Ghi 4 số nguyên x1, y1, x2 ,y2 lần lượt là toạ độ đỉnh dưới bên trái và đỉnh trên bên phải của HCN i. (Các số ghi trên một dòng cách nhau ít nhất một dấu cách)
Kết quả: Ghi vào tệp HCN.out dãy các hình chữ nhật sau khi sắp xếp.
Ý tưởng:
- Lưu toạ độ các đỉnh đa giác vào mảng a
- Tính diện tích hình chữ nhật theo công thức:
- Sắp xếp mảng a tăng dần theo diện tích
Ý tưởng:
Dạng 3. Xác định diện tích phủ bởi các hình chữ nhật
Phương pháp: Giả sử có n hình chữ nhật. Để tính diện tích phủ bởi n hình chữ nhật ta làm như sau:
Bước 1. Sử dụng a,b lần lượt là các mảng lưu hoành độ và tung độ các đỉnh hình chữ nhật (mỗi hình chữ nhật chỉ cần lưu toạ độ 2 đỉnh đối diện qua tâm hình chữ nhật).
Bước 2. Sắp xếp mảng a,b theo thứ tự tăng dần
Bước 3. Lần lượt kiểm tra các hình chữ nhật có toạ độ đỉnh trên bên phải (xi+1,yi+1) và toạ độ đỉnh dưới bên phải là (xi,yi) với 1 ≤i ≤n-1. Nếu hình chữ nhật này thuộc một trong các hình chữ nhật ban đầu thì cộng thêm vào phần diện tích đang cần tìm diện tích của hình chữ nhật con này.
Ví dụ 1. Diện tích phủ bởi các hình chữ nhật
Trong mặt phẳng toạ độ trực chuẩn, cho N hình chữ nhật có các cạnh song song với trục toạ độ. Mỗi HCN được xác định bởi toạ độ đỉnh dưới bên trái và đỉnh trên bên phải của nó. Hãy tính diện tích phần mặt phẳng bị phủ bởi các HCN trên.
Dữ liệu: Cho trong file HCN.inp gồm N+1 dòng.
- Dòng 1: Chứa số N
-Dòng i+1 (1 ≤i ≤N): Ghi 4 số nguyên x1,y1,x2,y2 lần lượt là toạ độ đỉnh dưới bên trái và đỉnh trên bên phải của HCN i. Các số ghi trên một dòng cách nhau ít nhất một dấu cách.
Kết quả: Đưa ra màn hình diện tích phần mặt phẳng bị phủ bởi hình chữ nhật trên.
Ý tưởng:
- Lập mảng X[1..2n], Y[1..2n] lần lượt chứa hoành độ, tung độ các hình chữ nhật
- Lưu toạ độ ban đâu các hình chữ nhật vào mảng a
- Sắp xếp mảng X,Y tăng dần
- Lần lượt kiểm tra các hình chữ nhật có toạ độ đỉnh trên bên phải (xi+1,yi+1) và toạ độ đỉnh dưới bên phải là (xi,yi) với 1 ≤i ≤n-1. Nếu hình chữ nhật này thuộc một trong các hình chữ nhật ban đầu thì cộng thêm vào phần diện tích đang cần tìm diện tích của hình chữ nhật con này.
Chương trình:
Ví dụ 2. Phủ S
Trên mặt phẳng tọa độ, một hình chữ nhật với các cạnh song song với các trục toạ độ được xác định bởi hai điểm đối tâm: đỉnh góc trên bên trái và đỉnh góc dưới bên phải. Cho N hình chữ nhật song song với các trục toạ độ. Phủ S của các hình chữ nhật có diện tích nhỏ nhất chứa N hình chữ nhật đã cho.
Dữ liệu vào: Đọc từ tệp PHUCN.INP có cấu trúc:
- Dòng đầu tiên chứa N (N ≤30);
- Trong N dòng tiếp theo, mỗi dòng ghi 4 số là toạ độ của hai đỉnh đối tâm của một hình chữ nhật, các số này là các số nguyên có trị tuyệt đối không quá 100.
Kết quả: Ghi ra tệp văn bản PHUCN.OUT
- Dòng 1 ghi toạ độ hai đỉnh đối tâm của phủ S các hình chữ nhật
- Dòng 2 ghi diện tích của phần hình S không nằm trong hình chữ nhật nào trong N hình đã cho
- Ý tưởng:
- Xác định hình chữ nhật H nhỏ nhất bao tất cả các hình chữ nhật ban đầu:
Gọi minx,maxx lần lượt là hoành độ nhỏ nhất và lớn nhất trong các hoành độ các đỉnh hình chữ nhật đã cho; miny, maxy lần lượt là tung độ nhỏ nhất và lớn nhất trong các tung độ các đỉnh hình chữ nhật đã cho. Khi đó hình H có toạ độ đỉnh dưới trái là (minx,miny) và đỉnh trên phải là (max,maxy). Đó là phủ S cần tìm.
- Tính diện tích hình H là (maxx-minx)(maxy-miny)
- Tính diện tích s phủ bởi các hình chữ nhật (đã nêu rõ ở phương pháp chung)
- Phần diện tích cần tìm là: s1:=abs((maxx-minx)*(maxy-miny))-s
- Chương trình:
Ví dụ 3. Diện tích phủ bởi các hình tròn
Trên mặt phẳng cho N hình tròn. Tính diện tích phần mặt phẳng bị phủ bởi các hình tròn trên.
Dữ liệu: Cho trong file INP.BL3 dòng đầu là số lượng hình tròn, từ dòng thứ 2 trở đi mỗi dòng chứa 3 số nguyên dương là tọa độ x, y của tâm và bán kính của từng hình tròn (các số trên cùng một dòng ghi cách nhau ít nhất 1 dấu cách)
Kết quả: Xuất ra màn hình
- Ý tưởng:
- Tìm hình chữ nhật nhỏ nhất có các cạnh song song với các trục toạ độ và chứa toàn bộ N hình tròn
- Chia hình chữ nhật này thành lưới các ô vuông có cạnh 0.1 đơn vị, với mỗi ô thuộc hình chữ nhật kiểm tra xem ô này có thuộc vào hình tròn nào đó hay không, nếu có thì tăng diện tích cần tính lên 0.01 đơn vị.
- Chương trình
Dạng 4. Xác định đa giác nhỏ nhất bao tất cả các điểm, đa giác đã cho
Phương pháp: Cho N điểm A1, A2, ..., AN trên mặt phẳng. Để xác định một đa giác không tự cắt chứa một số điểm đã cho và bao tất cả các điểm còn lại ta làm như sau:
Bước 1. Tìm điểm có tung độ nhỏ nhất. Điểm đó sẽ là đỉnh đa giác
Bước 2. Giả sử ta đã chọn được điểm PM. Tìm điểm Pi sao cho góc hợp bởi PMPi và trục hoành là nhỏ nhất và đồng thời góc này phải lớn hơn góc hợp bởi PMPM-1 và trục hoành. Điểm Pi sẽ là một đỉnh của đa giác.
Bước 3. Lấy kết quả là dãy các đỉnh P tìm được.
Lưu ý: Với bài toán tìm đa giác bao nhau thì cần ghi nhớ đa giác a bao đa giác b khi mọi điểm trong đa giác b đều nằm trong đa giác a.
Ví dụ 1. Đa giác không tự cắt
Cho N điểm A1, A2, ..., AN trên mặt phẳng. Các điểm đều có toạ độ nguyên và không có 3 điểm bất kỳ trong chúng thẳng hàng. Hãy viết chương trình thực hiện các công việc sau đây: Xác định một đa giác không tự cắt có đỉnh là một số điểm trong các điểm đã cho và chứa tất cả các điểm còn lại và có chu vi nhỏ nhất. Hãy tính diện tích đa giác này.
Dữ liệu: cho trong tệp HCN.INP gồm n+1 dòng
+ Dòng 1: Chứa số N
+ Dòng i+1 (1≤ i ≤ N): Ghi 2 chữ số nguyên xi,yi là toạ độ đỉnh Ai.
Các số trên cùng một dòng cách nhau một khoảng trắng.
Kết quả: Xuất ra tệp HCN.Out
+ Dòng 1: Ghi 3 số K, V, S với K là số đỉnh đa giác tìm được, V là chu vi, S là diện tích c