bzoj1597

首先不难想到排序，这种无规律的东西一般都要转化为有规律才好做

首先以x为第一关键字，y为第二关键字升序排序

拍完序我们发现，若存在两块土地i,j

x[i]<=x[j],y[i]<=y[j],那么土地i的购买一定可以忽略（因为价格是由x,y的乘积决定的）

剔除掉不需考虑的土地，不难发现剩下的土地x是升序而y是降序的

然后就可以dp了

f[i]=min(f[k]+x[i]*y[k+1]); (0<=k<=i-1)

显然这个是很容易用斜率优化的，不多说了

var q,st:array[0..50010] of longint;
    x,y,f:array[0..50010] of int64;
    w,n,t,h,r,i:longint;

procedure swap(var a,b:int64);
  var c:longint;
  begin
    c:=a;
    a:=b;
    b:=c;
  end;

procedure sort(l,r: longint);
  var i,j: longint;
      p,q:int64;
  begin
    i:=l;
    j:=r;
    p:=x[(l+r) shr 1];
    q:=y[(l+r) shr 1];
    repeat
      while (x[i]<p) or (x[i]=p) and (y[i]<q) do inc(i);
      while (p<x[j]) or (p=x[j]) and (q<y[j]) do dec(j);
      if not(i>j) then
      begin
        swap(x[i],x[j]);
        swap(y[i],y[j]);
        inc(i);
        j:=j-1;
      end;
    until i>j;
    if l<j then sort(l,j);
    if i<r then sort(i,r);
  end;

function check(l,r:longint):double;
  begin
    check:=(f[l]-f[r])/(y[st[r+1]]-y[st[l+1]]);
  end;

begin
  readln(n);
  for i:=1 to n do
    readln(x[i],y[i]);
  sort(1,n);
  t:=1;
  st[1]:=1;
  for i:=2 to n do
  begin
    while (t>0) and (x[i]>=x[st[t]]) and (y[i]>=y[st[t]]) do dec(t);
    inc(t);
    st[t]:=i;
  end;
  f[0]:=0;
  r:=0;
  h:=0;
  for i:=1 to t do
  begin
    while (h<r) and (check(q[h+1],q[h])<=x[st[i]]) do inc(h);
    w:=q[h];
    f[i]:=f[w]+y[st[w+1]]*x[st[i]];
    while (h<r) and (check(i,q[r])<check(q[r],q[r-1])) do dec(r);
    inc(r);
    q[r]:=i;
  end;
  writeln(f[t]);
end.