值最小的,还有high[i,j]
再令f[i,j]表示第j个点用i个矩形覆盖所需的最小面积
状态转移方程是
f[i,j]=max{f[i-1,k]+S(k+1,j)}S表示从k+1个点到j各点的矩形面积
还有矩形边不能重合也处理了
但结果是4 5两个点过不了
源程序如下:
var
x,y:array[1..50] of longint;
i,j,k,n,g,min,min1,min2:longint;
d:array[1..50]of boolean;
f:array[1..4,0..50] of record
n,low,high:longint;
end;
Low,high:array[1..50,1..50]of longint;
pp:boolean;
procedure qs(s,t:longint);
var
i,j,z1,z2:longint;
begin
i:=s;
j:=t;
z1:=x[i];
z2:=y[i];
while i<j do
begin
while ((i<j)and(z1<x[j]))or((i<j)and(z1=x[j])and(z2<y[j])) do
dec(j);
if i<j
then begin
x[i]:=x[j];
y[i]:=y[j];
inc(i);
end;
while ((i<j)and(x[i]<z1))or((i<j)and(z1=x[i])and(y[i]<Z2)) do
inc(i);
if i<j
then begin
x[j]:=x[i];
y[j]:=y[i];
dec(j);
end;
end;
x[i]:=z1;
y[i]:=z2;
if i-1>s
then qs(s,i-1);
if j+1<t
then qs(j+1,t);
end;
function ai(i,j:longint):longint;
begin
ai:=(high[i,j]-low[i,j])*(x[j]-x[i]);
end;
procedure init;
var
i,j,k,min,max:longint;
begin
fillchar(d,sizeof(d),true);
readln(n,g);
for i:=1 to n do
readln(x[i],y[i]);
qs(1,n);
for i:=1 to n-1 do
if x[i]=x[i+1]
then d[i]:=false;
for i:=1 to n do
for j:=i to n do
begin
min:=123456789;
max:=-123456789;
for k:=i to j do
begin
if y[k]>max
then max:=y[k];
if y[k]<min
then min:=y[k];
end;
low[i,j]:=min;
high[i,j]:=max;
end;
for i:=1 to n do
begin
f[1,i].n:=ai(1,i);
f[1,i].high:=high[1,i];
f[1,i].low:=low[1,i];
end;
end;
begin
init;
for i:=2 to n do
for j:=2 to g do
begin
min:=123456789;
for k:=1 to i-1 do
begin
pp:=true;
if not(d[k])
then if (low[k+1,i]<=f[j-1,k].high)or(high[k+1,i]>=f[j-1,k].low)
then pp:=false;
if pp
then if ai(k+1,i)+f[j-1,k].n<min
then begin
min:=ai(k+1,i)+f[j-1,k].n;
min1:=high[k+1,i];
min2:=low[k+1,i];
end;
end;
f[j,i].n:=min;
f[j,i].high:=min1;
f[j,i].low:=min2;
end;
writeln(f[g,n].n);
end.