littlelee
Admin
Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 29
Đến từ : Nghĩa địa
 |  Tiêu đề: Giải bài diện tích của n hình chữ nhật  Sun 28 Mar 2010, 12:28 | |
| Đề: - Trích dẫn :
- Trong mặt phẳng tọa độ xOy, cho n hình chữ nhật có các cạnh song song với các trục tọa độ. Mỗi hình chữ nhật được xác định bằng hai đỉnh: trên trái và dưới phải của nó. Tọa độ của các đỉnh là số nguyên và có giá trị tuyệt đối không quá 1000. Yêu cầu là hãy xác định diện tích bị che phủ bởi n hình chữ nhật trên.
Với bài này thì ta sẽ gặp khó khăn khi các hình chữ nhật chồng lên nhau. Để giải quyết vấn đề đó, ta sẽ dùng mảng để lưu trữ các ô diện tích đã tính rồi. Giải thuật: dùng mảng 2 chiều để lưu trữ vùng diện tích chồng lên mặt phẳng của mỗi hcn bằng cách cho ô đó có giá trị đặc biệt nào đó. Sau đó ta sẽ đếm số các ô có giá trị đặc biệt này, đó chính là dienẹ tích cần tìm. Tuy nhiên có thể cải tiến một chút, nếu ta gán hết tất cả rồi mới duyệt thì sẽ tốn thời gian. Để đỡ tốn thời gian, ta sẽ duyệt ngay lúc gán giá trị đặc biệt, nếu ô đó chưa có giá trị đặc biệt thì tăng biến đếm rồi gán, nếu đã có rồi thi ko làm gì hết. Sau khi nhập hết tất cả các hcn thì biến đếm đã có giá trị cần in ra. Bài cụ thể: - Code:
-
program dien_tich_n_hcn;
uses crt;
const max=100;
var a:array[-max..max,-max..max] of char;
i,j,n,m,g,h,k,l:integer; dem:longint;
procedure nhap;
begin
clrscr; dem:=0;
fillchar(a,sizeof(a),'.');
write('nhap vao so luong hcn: ');readln(n);
writeln;
for m:=1 to n do
begin
writeln('Nhap vao toa do cua hcn thu ',m);
write('nhap vao hoanh do dinh tren trai: ');readln(g);
write('nhap vao tung do dinh tren trai: ');readln(h);
write('nhap vao hoanh do dinh duoi phai: ');readln(k);
write('nhap vao tung do dinh duoi phai: ');readln(l);
for i:=g to k-1 do
for j:=h downto l+1 do
if a[i,j]='.' then begin a[i,j]:='*';inc(dem); end;
writeln;
end;
end;
procedure xuat;
begin
writeln('Dien tich cua cac hinh chu nhat tren la: ',dem);
readln;
end;
begin
nhap;
xuat;
end. | |
|
littlelee
Admin
Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 29
Đến từ : Nghĩa địa
| | Tiêu đề: Re: Giải bài diện tích của n hình chữ nhật Sun 28 Mar 2010, 12:30 | |
| Lưu ý là bài này chỉ chạy được với dữ liệu vừa thôi. | |
|
