littlelee
Admin
Tổng số bài gửi : 415
Join date : 20/12/2009
Age : 29
Đến từ : Nghĩa địa
 |  Tiê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. | |
|
administrators
Gà nhỏ
Tổng số bài gửi : 29
Join date : 15/03/2010
| | Tiê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. | |
|
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: 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 ^^ ). | |
|
administrators
Gà nhỏ
Tổng số bài gửi : 29
Join date : 15/03/2010
| | Tiê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 | |
|
hoangtin14
Mèo con
Tổng số bài gửi : 96
Join date : 08/02/2010
Age : 29
Đến từ : Bình Định
| | Tiê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ự đó. | |
|
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: 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. | |
|
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: 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ỉ. | |
|
Hovanthong
Admin
Tổng số bài gửi : 101
Join date : 25/07/2010
Age : 30
Đến từ : Hưng nguyên-Nghệ An
| | Tiê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.
| |
|
Sponsored content
| | Tiêu đề: Re: Diện tích của n hình chữ nhật | |
| |
|
