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 | 
 

 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 đề: Diện tích của n hình chữ nhật   Thu 18 Mar 2010, 13:30

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ề Đầu Trang Go down
administrators
Gà nhỏ


Tổng số bài gửi : 29
Join date : 15/03/2010

Bài gửiTiêu đề: Re: Diện tích của n hình chữ nhật   Thu 18 Mar 2010, 14:17

littlelee không nên post bài này. Bài này phải dùng đến cấu trúc dữ liệu đặc IT để giải. Bạn post lên các bạn lớp 9 đọc xong ối máu chết vì bị ngộ độc kiến thức đấy.
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: Diện tích của n hình chữ nhật   Thu 18 Mar 2010, 14:27

Không đâu. administrator xem lại đi. Các số ở đây đều là số nguyên cơ mà. Hơn nữa, giới hạn dữ liệu là không quá 1000. Bài này có cách giải rất dễ đấy. Ở đây, mình muốn các bạn giải bằng những cách tương tự như vậy (hoặc hay hơn càng tốt ^^ ).
Về Đầu Trang Go down
administrators
Gà nhỏ


Tổng số bài gửi : 29
Join date : 15/03/2010

Bài gửiTiêu đề: Re: Diện tích của n hình chữ nhật   Thu 18 Mar 2010, 14:34

Đó không phải là giới hạn dữ liệu. Cái quan trọng là n kìa
Về Đầu Trang Go down
hoangtin14
Mèo con


Tổng số bài gửi : 96
Join date : 08/02/2010
Age : 21
Đến từ : Bình Định

Bài gửiTiêu đề: Re: Diện tích của n hình chữ nhật   Thu 18 Mar 2010, 21:37

Sẵn tiện admin giải luôn bài số miền chia bởi n đường thẳng luôn đi. Thấy hai bài này gần tương tự đó.
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: Diện tích của n hình chữ nhật   Fri 19 Mar 2010, 14:22

administrators đã viết:
Đó không phải là giới hạn dữ liệu. Cái quan trọng là n kìa

Ô đâu, nếu n=1000 (đối với lớp 9 thì đó là rất lớn) thì vẫn chạy bình thường mà. Đâu có quan trọng chi.
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: Diện tích của n hình chữ nhật   Fri 19 Mar 2010, 14:24

hoangtin14 đã viết:
Sẵn tiện admin giải luôn bài số miền chia bởi n đường thẳng luôn đi. Thấy hai bài này gần tương tự đó.

Uhm, mình sẽ post lên rồi giải sau. Mà không phải hai bài này tương tự đâu. Bài này rất dễ đó. Bài miền được chia bởi n đường thẳng khó hơn nhiều. Mặc dù vậy thì chắc chả nhằm nhò gì với ad đâu nhỉ.
Về Đầu Trang Go down
Hovanthong
Admin
Admin


Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 22
Đến từ : Hưng nguyên-Nghệ An

Bài gửiTiêu đề: Re: Diện tích của n hình chữ nhật   Mon 26 Jul 2010, 21:19

Code đơn giản nhất:
Code:

Const Maxn=10000;

Type Toa_do = record x1,y1,x2,y2:integer;end;
mang=array[1..2*maxn] of integer;
var N,s:integer;
a:array[1..maxn] of toa_do;
X,Y:mang;

Procedure doc_dl;
var  i:integer;
begin
readln(n);
for i:=1 to n do
readln(a[i].x1,a[i].y1,a[i].x2,a[i].y2);
end;

Procedure Sapxep(Var T:Mang);
Var i,j,TG,m:integer;
Begin
m:=2*n;
for i:=1 to m-1 do
for j:=i+1 to m do
if T[i]>T[j] then
begin
TG:=T[i];
T[i]:=T[j];
T[j]:=TG;
end;
end;

function Kiemtra_thuoc(i,j:integer):boolean;
var k:integer;
begin
Kiemtra_thuoc:=true;
for k:=1 to N do
if (a[k].x1<=x[i-1]) and (X[i]<=a[k].x2)and (a[k].y1<=y[j-1])and(Y[j]<=a[k].y2) then exit;
Kiemtra_thuoc:=false;
end;

Procedure Xuly;
var i,j:integer;
Begin
for i:=1 to N do
begin
X[i*2-1]:=a[i].x1;
X[i*2]:=a[i].x2;
Y[i*2-1]:=a[i].y1;
Y[i*2]:=a[i].y2;
end;
Sapxep(X); Sapxep(Y);
for i:=2 to 2*N do
for j:=2 to 2*N do
if Kiemtra_thuoc(i,j) then S:=s+(X[i]-X[i-1])*(Y[j]-Y[j-1]);
end;
Begin
doc_dl;
s:=0;
Xuly;
Write(S);
End.


Về Đầu Trang Go down
http://thongtra.forum-viet.com
Sponsored content




Bài gửiTiêu đề: Re: Diện tích của n hình chữ nhật   Today at 18:49

Về Đầu Trang Go down
 
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