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

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ủa nó. + Dòng i+1(1≤ i ≤ K): Ghi toạ độ của đỉnh đa giác. - Ý tưởng: - Tìm điểm có tung độ nhỏ nhất. Điểm đó sẽ là đỉnh đa giác - 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. Ví dụ 2. Đa giác bao nhau Cho N đa giác thoả mãn các tính chất - Với 2 đa giác bất kỳ luôn có một đa giác mà mọi điểm của nó nằm trong đa giác kia. - Các cạnh của chúng không có điểm chung. Bài toán đặt ra là: Với mỗi đa giác i, có bao nhiêu đa giác bao nó? (i nằm trong bao nhiêu đa giác) Dữ liệu vào: Ghi trong tập tin văn bản Dagiac.Inp. - Dòng đầu tiên ghi số tự nhiên N (3≤N≤10000). - Trên N dòng tiếp theo: Dòng thứ i+1 ghi thông tin về đa giác có số hiệu thứ i. Bao gồm số đầu tiên Si là số đỉnh của đa giác (Si≥3), Si cặp số nguyên tiếp theo lần lượt là hoành độ và tung độ các đỉnh của đa giác. Các số trên cùng dòng cách nhau bởi ít nhất một khoảng trắng. Dữ liệu ra: Ghi trong tập tin Dagiac.Out - Gồm N dòng - Dòng thứ i: Ghi số lượng đa giác bao đa giác i. - Ý tưởng: - Sử dụng các mảng a,vt,kq (với a[i] lưu giá trị hoành độ nhỏ nhất của các đỉnh của đa giác thứ i, vt[i] chỉ đa giác thứ i, mảng kq lưu kết quả) - Thực hiện sắp xếp các đa giác theo thứ tự tăng dần của giá trị hoành độ nhỏ nhất của các đỉnh của các đa giác. - Do theo điều kiện bài toán là với 2 đa giác bất kỳ luôn có một đa giác mà mọi điểm của nó nằm trong đa giác kia nên KQ[vt[i]] =i-1 - Chương trình: Ví dụ 3. Hình chữ nhật bao nhau Cho N hình chữ nhật trên mặt phẳng mà các cạnh song song với các trục toạ độ. Biết hình chữ nhật i bao hình chữ nhật j nếu cả 4 đỉnh của hình chữ nhật j đều nằm trong hình chữ nhật i hoặc nằm trên cạnh của hình chữ nhật i. Một dãy các hình chữ nhật được gọi là hình chữ nhật bao nhau chiều dài k (k≥1) nếu dãy này gồm các hình chữ nhật H1, H2, ..., Hk sao cho hình chữ nhật i bao hình chữ nhật i+1 với i=1 ... (k-1). Hãy tìm số k lớn nhất nói trên. Dữ liệu vào: Được cho trong tập tin HCN.INP - Dòng thứ nhất ghi số N (1≤N≤1000). - N dòng tiếp theo, dòng thứ i ghi 4 số nguyên x1, y1, x2, y2 (-10000< x1,y1,x2,y2<10000) lần lượt là hoành độ, tung độ các đỉnh trái trên, phải dưới của hình chữ nhật. Kết quả: Được ghi vào tệp văn bản HCN.OUT gồm một dòng chứa số nguyên duy nhất là số k tìm được hoặc số -1 nếu không tồn tại số k thoả điều kiện đề bài. - Ý tưởng: - Tính diện tích các hình chữ nhật (HCN) - Sắp xếp lại các HCN theo thứ tự không giảm của diện tích các HCN - Lập hàm kiểm tra HCN i bao HCN j, thoả mãn điều kiện: (x1[i]=y1[j]) and (x2[i]>=x2[j]) and (y2[i]<=y2[j]) - Xác định số lượng các HCN bao HCN i và lưu vào phần tử mảng kq[i] biết rằng: nếu thì kq[i]:=kq[j]+1 - Chương trình: Ví dụ 4. Hình chữ nhật bao nhau Hình chữ nhật A bao hình chữ nhật B nếu mọi điểm thuộc hình chữ nhật B đều nằm trong hoặc thuộc hình chữ nhật A. Trong mặt phẳng Oxy cho n hình chữ nhật có các cạch song song với các trục toạ độ. Yêu cầu: 1. Tìm số hình chữ nhật bao nhau nhiều nhất (số lượng hình phải >1). 2. Trong số các tập hình chữ nhật bao nhau, tìm tập các hình chữ nhật bao nhau có tổng diện các diện tích của các hình chữ nhật trong tập là lớn nhất. 3. Tìm hiệu diện tích của hình chữ nhật nhỏ nhất bao tất cả các hình chữ nhật đã cho với diện tích của phần mặt phẳng bị phủ bởi các hình chữ nhật đã cho. Dữ liệu vào: Cho trong tệp văn bản HCN.IN - Dòng đầu: n (số lượng hình chữ nhật, 1≤N≤1000) - n dòng tiếp theo: Mỗi dòng chứa 4 số dạng a, b, c, d (a, b, c, d là các số nguyên) với (a, b) và (c, d) là toạ độ của hai đỉnh đối tâm của hình chữ nhật. Kết quả: Xuất ra tệp văn bản HCN.Out - Dòng đầu: Cho biết tập các hình chữ nhật bao nhau nhiều nhất theo dạng k l m n ... với ý nghĩa-Hình chữ nhật thứ k thuộc hình chữ nhật thứ l, hình chữ nhật thứ l thuộc hình chữ nhật thứ m, hình chữ nhật thứ m thuộc hình chữ nhật n ... nếu không có thì ghi từ "khong" - Dòng thứ 2: Cho biết tập các hình chữ nhật bao nhau có tổng các diện tích của các hình chữ nhật trong tập hợp là lớn nhất theo qui cách như dòng thứ nhất. Nếu không thì ghi số 0. - Dòng thứ 3: Chứa con số biểu diễn hiệu diện tích hình chữ nhật nhỏ nhất bao tất cả hình chữ nhật đã cho với diện tích của phần mặt phẳng bị phủ bởi các hình chữ nhật đã cho. - Ý tưởng: - Lưu tọa độ các đỉnh hình chữ nhật vào 4 mảng x1,y1,x2,y2 - Dùng mảng bao(n,n) để đánh dấu các hình chữ nhật bao nhau: Với bao[i,j]=1 có nghĩa hình chữ nhật i bao hình chữ nhật j, bao[i,j]=0 thì ngược lại. - Dãy hình chữ nhật thứ i, k, j gọi là bao nhau nếu (Bao[i,k]+bao[k,j]>bao[i,j]) và (bao[i,k]>0) và (bao[k,j]>0). Sử dụng mảng KQ để lưu các hình chữ nhật k thoả mãn - Hình chữ nhật nhỏ nhất bao tất cả các hình chữ nhật đã cho là hình chữ nhật có toạ độ góc dưới phải là (xmin,ymin) và toạ độ góc trên trái là (xmax,ymax) - Phương pháp tìm diện tích phủ đã trình bày ở dạng 3