Trên mặt phẳng tọa độ
cho N tam giác vuông cân, hai cạnh góc vuông song song với hai trục tọa độ,
cạnh huyền nằm ở bên phải tam giác. Cụ thể là nếu kí hiệu tam giác là ABC thì
ta qui định đỉnh A là đỉnh góc vuông, cạnh góc vuông AB song song với trục hoành
ox, cạnh góc vuông AC song song với trục tung oy, AB = AC = d. Mỗi tam giác
được mô tả bằng bộ ba số nguyên x, y, d trong đó (x,y) là tọa độ nguyên của
đỉnh A, d là chiều dài cạnh góc vuông.
|
TAMGIAC.INP
|
TAMGIAC.OUT
|
|
5
6 0 3
1 0 3
2 1 3
4 1 2
4 5 2
|
16.50
|
|
|
|
|
|
|
|
|
|
|
 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
y C
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
A
|
|
|
B
|
|
|
|
|
|
|
o
|
|
|
x
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Yêu cầu: Tính diện tích do các tam giác
phủ trên mặt phẳng tọa độ.
Dữ liệu vào: text file TAMGIAC.INP
Dòng đầu tiên: số tự nhiên N trong khoảng 2 .. 1000.
N dòng tiếp theo: mỗi dòng 3 số x y d cách nhau qua dấu cách, x và
y biến thiên trong khoảng -1000..1000, d trong khoảng 1..1000.
Dữ liệu ra: text file TAMGIAC.OUT chứa
một số thực duy nhất S là diện tích bị các tam giác phủ trên mặt phẳng tọa độ.
Thuật
toán
Tương tự như bài Các Hình chữ nhật. Với mỗi tam giác (x, y,
d) ta tạo ra hai đường song song với trục hoành và cắt trục tung tại các điểm y
và y+d, cụ thể là một đường chứa cạnh đáy và một đường đi qua đỉnh của tam
giác. Các đường thẳng này sẽ tạo ra các băng. Với mỗi tam giác (TG) ta cũng xét
tương tự như HCN, nghĩa là xét các băng chứa trong TG đó. Biến diện tích dt
được khai báo kiểu float vì các hình trong băng j sẽ là hình thang có đáy lớn là
e[j]-s[j], đáy nhỏ bằng đáy
lớn – h, h là chiều cao: h = y[j+1]-y[j]
= độ rộng của băng. Khi chuyển từ băng j lên băng j+1 ta phải chỉnh lại đầu
phải x2 của cạnh đáy TG thành x2 – h vì TG lúc này sẽ ngắn lại. Khi tính phần
giao nhau ta còn phải trừ đi diện tích của TG nằm ngoài phần giao đó. Hình vẽ cho ta thấy khi xét tam giác XYV và
băng giới hạn trong 2 đường thẳng TM và SE, thì làn (S, E) sẽ được mở rộng
thành làn (S, V). Diện tích trước đó của làn SE chính là diện tích hình thang
vuông TMES, nay làn (S,V) có diện tích của hình thang vuông TRVS. Như vậy ta đã
tính dôi ra phần diện tích tam giác MPQ. Dễ dàng xác định được diện tích z của tam giác
vuông cân này: Đặt k = MP = PQ, ta có z = k2/2.Ta xác định k như
sau. k = MP = TP -
TM = SX-TM
= x-(e[j]-h),
trong đó h là chiều rộng của băng j đang xét, h = y[j+1]-y[j],
e[j] là điểm cuối của làn đang xét, x là hoành độ của đỉnh góc vuông trong tam giác XYV đang
xét.
Độ phức
tạp: N2.
(* Pascal *)
(**********************************************
Cac
tam giac vuong can
*********************************************)
program TamGiacVuongCan;
uses crt;
const mn = 2001; bl = #32; nl = #13#10;
fn = 'TamGiac.inp'; gn = 'TamGiac.out';
type TG = record
x,y: integer;
d: integer;
end;
mtg1 = array[0..mn] of
TG;
mi1 = array[0..mn] of
integer;
mr1 = array[0..mn] of
real;
var
n,m: integer; { n - so
tam giac }
y: mi1;
{ m - so diem y, max(m) = 2n }
t: mtg1;
f,g: text;
dt: real; // tong dien
tich
(*--------------------------------------------
To chuc du lieu cho
Bang i
s[i], e[i] - can trai
va phai cua Bang
----------------------------------------------*)
s, e: mi1;
function Max(a,b: integer): tự viết
(*-----------------------------
Xen them v vao day
da sap tang y[1..m]
------------------------------*)
procedure Insert(v: integer); tự viết
procedure Doc;
var i: integer;
begin
assign(f,fn); reset(f);
readln(f,n);
m := 0;
for i := 1 to n do
begin
readln(f,t[i].x,t[i].y,t[i].d);
Insert(t[i].y);
Insert(t[i].y + t[i].d);
end;
close(f);
end;
{ Sap cac TG tang theo x }
procedure SortByX(d,c: integer); tự viết
{ Tim nhi phan v trong y[1..m] }
function BinSearch(v: integer): integer; tự viết
(*---------------------------------------
Xet hinh Tam giac h:
tinh cac o
hinh h phu tren cac Bang
--------------------------------------*)
procedure Hinh(x1,y1,d: integer);
var i,y2,x2,h,k: integer;
begin
{ Tim xuat hien cua toa
do y1 trong cac lan }
i := BinSearch(y1);
x2 := x1 + d; y2 := y1 + d;
while (y[i] < y2) do
begin
h := y[i + 1] - y[i];
if (x1 <= e[i]) then
begin
k := x1 - (e[i] - h);
e[i] := Max(e[i], x2);
if (k > 0) then
dt := dt - (real(k * k) / 2);
end
else
begin
if (e[i] > s[i])
then
dt := dt + h * (2 * (e[i] - s[i]) - h) / 2;
s[i] := x1; e[i] :=
x2;
end;
i := i + 1; x2 := x2 -
h;
end;
end;
procedure XuLi;
var i, h: integer;
begin
for i := 1 to m do
begin s[i] := -maxint; e[i]
:= s[i]; end;
dt := 0.0;
{ Duyet cac TG }
for i := 1 to n do
Hinh(t[i].x,t[i].y,t[i].d);
{ Tong hop ket qua }
for i := 1 to m-1 do
begin
h := y[i + 1] - y[i];
if (e[i] > s[i]) then
dt := dt + h * (2 * (e[i] - s[i]) - h) / 2;
end;
end;
procedure Ghi;
begin
assign(g,gn); rewrite(g);
writeln(g,dt:0:2); close(g)
end;
BEGIN
Doc; SortByX(1,n); XuLi; Ghi;
END.
Nguồn:
SÁNG TẠO
TRONG THUẬT TOÁN
VÀ
LẬP TRÌNH
Không có nhận xét nào:
Đăng nhận xét