Trở về đầu

foto1 foto2 foto3 foto4 foto5
Nguyễn Tô Sơn - Giảng viên Đại học Sư phạm Hà Nội. SĐT: 091.333.2869

HỌC TIN CÙNG THỦ KHOA

Thành tích hôm nay, Thành công ngày mai !

Tìm kiếm

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

Bản quyền thuộc về Nguyễn Tô Sơn, Đại học Sư phạm Hà Nội. Điện thoại: 091.333.2869