平面上的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.
|