bzoj2395

分组赛时学到的最小乘积生成树模型，感觉这个思路非常神，可以说是数形结合的经典问题

由于生成树有两个权值，我们把每个生成树的权值表示成点坐标（sa,sb)

显然我们知道，乘积最小，那么点必然落在下凸壳上

但由于点太多，graham之类要先知道所有点再求凸包的算法就失效了

于是我们使用quickhull算法，这个算法只要知道凸包上的两个点就可以扩展出下一个点，然后不断分治即可扩展出所有点

显然，以a为关键字和以b为关键字的最小生成树一定是凸包上的两个点i，j

根据quickhull算法，下一个凸包上的点就是离直线ij距离最大的点

转化一下，就是与ij垂直的向量点积最小的点

显然我们只要以此为关键字求最小生成树即可

这样我们不断分治下去，直到无法扩展为止，这样就找到了答案

但我好像被卡常了（还是写的太囧……），总之tle了……

type node=record
       x,y,w,a,b:longint;
     end;
     point=record
       x,y:longint;
     end;

var e:array[0..10010] of node;
    fa:array[0..210] of longint;
    i,n,m:longint;
    ans,p1,p2:point;

function getf(x:longint):longint;
  begin
    if fa[x]<>x then fa[x]:=getf(fa[x]);
    exit(fa[x]);
  end;

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

function cmp(x,y:node):boolean;
  begin
    if x.w=y.w then exit(x.a<y.a);
    exit(x.w<y.w);
  end;

procedure sort(l,r:longint);
  var i,j:longint;
      x:node;
  begin
    i:=l;
    j:=r;
    x:=e[(l+r) shr 1];
    repeat
      while cmp(e[i],x) do inc(i);
      while cmp(x,e[j]) do dec(j);
      if not(i>j) then
      begin
        swap(e[i],e[j]);
        inc(i);
        dec(j);
      end;
    until i>j;
    if l<j then sort(l,j);
    if i<r then sort(i,r);
  end;

function mintree:point;
  var i,j,sa,sb,x,y:longint;
  begin
   {for j:=1 to m do
    writeln(e[j].w);  }
    j:=0;
    sa:=0;
    sb:=0;
    for i:=1 to n do
      fa[i]:=i;
    i:=0;
    while i<n-1 do
    begin
      inc(j);
      x:=getf(e[j].x);
      y:=getf(e[j].y);
      if x<>y then
      begin
        fa[x]:=y;
        sa:=sa+e[j].a;
        sb:=sb+e[j].b;
        inc(i);
      end;
    end;
    mintree.x:=sa;
    mintree.y:=sb;
    if (int64(ans.x)*int64(ans.y)>int64(sa)*int64(sb)) or (int64(ans.x)*int64(ans.y)=int64(sa)*int64(sb)) and (ans.x>sa) then
    begin
      ans.x:=sa;
      ans.y:=sb;
    end;
  end;

function cross(a,b,c:point):int64;
  begin
    exit(int64(a.x-c.x)*int64(b.y-c.y)-int64(a.y-c.y)*int64(b.x-c.x));
  end;

procedure work(p1,p2:point);
  var i:longint;
      p:point;

  begin
    for i:=1 to m do
      e[i].w:=e[i].a*(p1.y-p2.y)+e[i].b*(p2.x-p1.x);
    sort(1,m);
    p:=mintree;
    if cross(p2,p,p1)>=0 then exit;
    work(p1,p);
    work(p,p2);
  end;

begin
  readln(n,m);
  for i:=1 to m do
  begin
    readln(e[i].x,e[i].y,e[i].a,e[i].b);
    inc(e[i].x);
    inc(e[i].y);
    e[i].w:=e[i].a;
  end;
  ans.x:=1000000007;
  ans.y:=1000000007;
  sort(1,m);
  p1:=mintree;
  for i:=1 to m do
    e[i].w:=e[i].b;
  sort(1,m);
  p2:=mintree;
  work(p1,p2);
  writeln(ans.x,' ',ans.y);
end.