Trở về đầu
Đề bài: Cho một đa giác lồi N đỉnh. Bằng các đường chéo không cắt nhau, ta có thể chia đa giác thành N–2 tam giác. Hãy xác định cách chia có tổng các đường chéo ngắn nhất.
Mời các bạn download tại: Click here
const fi = 'CHIADAGIAC.INP';
fo = 'CHIADAGIAC.OUT';
MAXN = 100;
oo = MAXINT;
var f:text;
n: integer;
a, b: array[1..MAXN] of real;
H: array[1..MAXN, 1..MAXN] of integer;
L: array[1..MAXN, 1..MAXN] of real;
//L[i, j] tong do dai cac duong cheo
//khi xet tu dinh i den dinh j
d: array[1..MAXN, 1..MAXN] of real;
//d la do dai duong cheo giua dinh i va j
procedure Nhap;
var i:integer;
begin
assign(f, fi); reset(f);
readln(f, n);
for i:= 1 to n do readln(f, a[i], b[i]);
close(f);
//a[n+1] := a[1];
//b[n+1] := b[1];
end;
function KhoangCach(i, j: integer):real;
begin
exit(sqrt(sqr(a[i]-a[j])+sqr(b[i]-b[j])));
end;
procedure TinhKhoangCachCacDuongCheo;
var i, j: integer;
begin
for i:= 1 to n do
begin
d[i, i]:= 0;
d[i, i mod n + 1]:= 0;
d[i mod n + 1, i]:= 0;
end;
for i:= 1 to n do
for j:= 1 to i-1 do
if (i <> j) and (abs(i-j) <> 1) then
begin
d[i, j]:= KhoangCach(i, j);
d[j, i]:= d[i, j];
end;
end;
function min(a, b:real):real;
begin
if a<b then exit(a) else exit(b);
end;
procedure QHD;
var i, j, m, k: integer;
tong :real;
begin
fillchar(L, sizeof(L), 0);
// m = j - i
for m:=3 to n-1 do
for i:=1 to n-m do
begin
j := i+m;
L[i,j] := +oo;
for k:= i to j-1 do
begin
tong:= L[i, k] + L[k,j] + d[i, k] + d[k, j];
if L[i, j] > tong then
begin
L[i, j]:= tong;
H[i, j]:= k;
end;
end;
end;
end;
procedure TruyVet(i, j:integer);
var k:integer;
begin
if j - i >= 3 then
begin
k:= H[i, j];
writeln(f, 'Noi dinh ', i, ' voi dinh ', k);
writeln(f, 'Noi dinh ', k, ' voi dinh ', j);
TruyVet(i, k);
TruyVet(k, j);
end;
end;
BEGIN
Nhap;
QHD;
assign(f, fo); rewrite(f);
writeln(f, L[1, n]:0:2);
TruyVet(1, n);
close(f);
END.