Diễn đàn tin học Nguyễn Văn Linh

The second house for every one
 
IndexTrợ giúpTìm kiếmThành viênĐăng kýĐăng Nhập

Share | 
 

 Giải bài diện tích của n hình chữ nhật

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiê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.
Về Đầu Trang Go down
littlelee
Admin
Admin


Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 21
Đến từ : Nghĩa địa

Bài gửiTiê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.
Về Đầu Trang Go down
 
Giải bài diện tích của n hình chữ nhật
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn đàn tin học Nguyễn Văn Linh :: Góc tin học :: Lớp chuyên tin-
Chuyển đến