Trang chủ   Sản phẩm   Phần mềm Dành cho nhà trường   Phần mềm Hỗ trợ học tập   Kho phần mềm   Liên hệ   Đăng nhập | Đăng ký

Tìm kiếm

School@net
Bảng giá phần mềm
Educations Software

Đại Lý - Chi Nhánh

Bản tin điện tử
 
Đăng nhập/Đăng ký
Bí danh
Mật khẩu
Mã kiểm traMã kiểm tra
Lặp lại mã kiểm tra
Ghi nhớ
 
Quên mật khẩu | Đăng ký mới

 
Giỏ hàng

Xem giỏ hàng


Giỏ hàng chưa có sản phẩm

 
Xem bài viết theo các chủ đề hiện có
  • Hoạt động của công ty (701 bài viết)
  • Sản phẩm mới (217 bài viết)
  • Dành cho Giáo viên (552 bài viết)
  • Lập trình Scratch (3 bài viết)
  • Mô hình & Giải pháp (155 bài viết)
  • IQB và mô hình Ngân hàng đề kiểm tra (126 bài viết)
  • Hỗ trợ khách hàng (482 bài viết)
  • TKB và bài toán xếp Thời khóa biểu (242 bài viết)
  • Học tiếng Việt (182 bài viết)
  • Thông tin khuyến mại (80 bài viết)
  • Download - Archive- Update (289 bài viết)
  • Các Website hữu ích (71 bài viết)
  • Cùng Học (98 bài viết)
  • Learning Math: Tin học hỗ trợ học Toán trong nhà trường (74 bài viết)
  • Thông tin tuyển dụng (55 bài viết)
  • School@net 15 năm (153 bài viết)
  • Mỗi ngày một phần mềm (7 bài viết)
  • Dành cho cha mẹ học sinh (123 bài viết)
  • Khám phá phần mềm (122 bài viết)
  • GeoMath: Giải pháp hỗ trợ học dạy môn Toán trong trường phổ thông (36 bài viết)
  • Phần mềm cho em (13 bài viết)
  • ĐỐ VUI - THƯ GIÃN (360 bài viết)
  • Các vấn đề giáo dục (1209 bài viết)
  • Bài học trực tuyến (1033 bài viết)
  • Hoàng Sa - Trường Sa (17 bài viết)
  • Vui học đường (276 bài viết)
  • Tin học và Toán học (220 bài viết)
  • Truyện cổ tích - Truyện thiếu nhi (181 bài viết)
  • Việt Nam - 4000 năm lịch sử (97 bài viết)
  • Xem toàn bộ bài viết (8179 bài viết)
  •  
    Thành viên có mặt
    Khách: 10
    Thành viên: 0
    Tổng cộng: 10
     
    Số người truy cập
    Hiện đã có 55798687 lượt người đến thăm trang Web của chúng tôi.

    PHƯƠNG PHÁP GIẢI TOÁN HÌNH HỌC BẰNG NGÔN NGỮ LẬP TRÌNH PASCAL (tiếp theo)

    Ngày gửi bài: 22/10/2010
    Số lượt đọc: 3283

    PHẦN II. MỘT SỐ DẠNG BÀI TOÁN HÌNH HỌC THƯỜNG GẶP

    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ủ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 (3N10000).

    - 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 (Si3), 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 (k1) 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 (1N1000).

    - 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]<=x1[j]) and (y1[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

    Chương trình

    Còn nữa

    Schoolnet (Theo TH&NT)



     Bản để in  Lưu dạng file  Gửi tin qua email


    Những bài viết khác:



    Lên đầu trang

     
    CÔNG TY CÔNG NGHỆ TIN HỌC NHÀ TRƯỜNG
     
    Phòng 1407 - Nhà 17T2 - Khu Trung Hoà Nhân Chính - Quận Cầu Giấy - Hà Nội
    Điện thoại: (024) 62511017 - Fax: (024) 62511081
    Email: school.net@hn.vnn.vn / thukhachhang@yahoo.com


    Bản quyền thông tin trên trang điện tử này thuộc về công ty School@net
    Ghi rõ nguồn www.vnschool.net khi bạn phát hành lại thông tin từ website này
    Site xây dựng trên cơ sở hệ thống NukeViet - phát triển từ PHP-Nuke, lưu hành theo giấy phép của GNU/GPL.