平面上的n个点用k个矩形覆盖的最小面积?

[复制链接]
发表于 2023-12-30 09:34:23 | 显示全部楼层 |阅读模式
平面上的n个点用k个矩形覆盖的最小面积?
程序如下:
programtg20024;
const maxn=50;
type pointset=array[1..maxn,1..2] of longint;
var
n,k,i,j,l:integer;
a:pointset;
f:array[1..maxn] of longint;
maxs,min,t:longint;
procedure init;
var i:integer;
     filename:string[20];
     f:text;
begin
readln(filename);
assign(f,filename);
reset(f);
readln(n,k);
for i:= 1 to n do
  readln(a[i,1],a[i,2]);
close(f);
end;
procedure sort(var x:pointset);
var i,j,m:integer;
   t1,t2,t3:integer;
begin
for i:=1 to n-1 do
  begin
   t1:=x[i,1];t2:=x[i,2];t3:=t2;m:=i;
   for j:= i+1 to n do
    if t3>x[j,2] then begin m:=j; t3:=x[j,2];end;
   if m<>i then
   begin x[i,1]:=x[m,1];x[i,2]:=x[m,2];x[m,1]:=t1;x[m,2]:=t2 end;
  end;
end;
function maxy(x0,xn:integer):integer;
var i,max:integer;
begin
max:=0;
for i:=x0 to xn do
   if max<a[i,1] then max:=a[i,1];
maxy:=max;
end;
function miny(x0,xn:integer):integer;
var i,min:integer;
begin
min:=32767;
for i:=x0 to xn do
   if min>a[i,1] then min:=a[i,1];
miny:=min;
end;
begin
init;
sort(a);
fillchar(f,sizeof(f),0);
maxs:=(a[n,2]-a[1,2])*(maxy(1,n)-miny(1,n));
for i:= 1 to n do
f:=(a[i,2]-a[1,2])*(maxy(1,i)-miny(1,i));
for i:=2 to k do
   for j:= n downto 1 do
     begin
        min:=maxs;
        for l:=i-1 to j-1 do
         begin
          t:=f[l]+(a[j,2]-a[l+1,2])*(maxy(l+1,j)-miny(l+1,j));
           if (t<min) and(a[l,2]<>a[l+1,2]) then min:=t;
         end;
       f[j]:=min;
      end;
writeln(f[n]);
end.

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表