HỌC TIN CÙNG THỦ KHOA

Đề 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.