bzoj1185

一遇到数学题和计算几何题我就要调半天……

玛雅，我真是太弱了……

基本思路很简单，先上凸包，然后矩形与凸包一边重合，然后旋转卡壳即可

然而我没怎么写过计算几何题，一开始写的各种囧，后来看了hzwer的写法才写得正常一些

一开始写囧，是找矩形的左右边界，用勾股定理算的，囧得不行；

后来发现可以用点积来判断，点积的几何意义：向量A在向量B上投影的长度*向量B的长度

然后就很好做了

 const eps=1e-8;

 type point=record

        x,y:double;

      end;

 var a:array[..] of point;

     q:array[..] of longint;

     p:array[..] of point;

     n,f1,f2,h,r,t,k,i:longint;

     tmp,ans,d,l,l1,l2:double;

 procedure swap(var a,b:point);

   var c:point;

   begin

     c:=a;

     a:=b;

     b:=c;

   end;

 function cmp(a,b:point):boolean;

   begin

     if abs(a.y-b.y)<eps then exit(a.x<b.x);

     exit(a.y<b.y);

   end;

 function cross(i,j,k,p:longint):double;

   begin

     exit((a[i].x-a[j].x)*(a[k].y-a[p].y)-(a[i].y-a[j].y)*(a[k].x-a[p].x));

   end;

 procedure sort(l,r:longint);

   var i,j:longint;

       x:point;

   begin

     i:=l;

     j:=r;

     x:=a[(l+r) shr ];

     repeat

       while cmp(a[i],x) do inc(i);

       while cmp(x,a[j]) do dec(j);

       if not(i>j) then

       begin

         swap(a[i],a[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 dis(a,b:point):double;

   begin

     exit(sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)));

   end;

 function mul(i,j,p,q:longint):double;

   begin

     exit((a[i].x-a[j].x)*(a[p].x-a[q].x)+(a[i].y-a[j].y)*(a[p].y-a[q].y));

   end;

 begin

   readln(n);

   for i:= to n do

     readln(a[i].x,a[i].y);

   sort(,n);

   ans:=1e15;

   t:=;

   q[]:=;

   for i:= to n do

   begin

     while (t>) and (cross(q[t],q[t-],i,q[t-])<eps) do dec(t);

     inc(t);

     q[t]:=i;

   end;

   k:=t;

   for i:=n- downto  do

   begin

     while (t>k) and (cross(q[t],q[t-],i,q[t-])<eps) do dec(t);

     inc(t);

     q[t]:=i;

   end;

 //  q[t+]:=q[];

 {  for i:=1 to t do

     writeln(a[q[i]].x,' ',a[q[i]].y);

   writeln(k); }

   k:=;

   h:=;

   r:=;

   for i:= to t- do

   begin

     d:=dis(a[q[i]],a[q[i+]]);

     while cross(q[i+],q[i],q[k mod t+],q[i])-cross(q[i+],q[i],q[k],q[i])>-eps do k:=k mod t+;

     while (mul(q[i+],q[i],q[r mod t+],q[i])-mul(q[i+],q[i],q[r],q[i])>-eps) do r:=r mod t+;

     if i= then h:=r;

     while (mul(q[i+],q[i],q[h mod t+],q[i])-mul(q[i+],q[i],q[h],q[i])<eps) do h:=h mod t+;

     l1:=mul(q[i+],q[i],q[h],q[i])/d;

     l2:=mul(q[i+],q[i],q[r],q[i])/d;

     l:=abs(cross(q[i+],q[i],q[k],q[i]))/d;

     tmp:=(l2-l1)*l;

     if ans>tmp then

     begin

       ans:=tmp;

      // writeln(tmp,' ',a[q[i]].x,' ',a[q[i]].y,' ',l2/d);

       p[].x:=a[q[i]].x+(a[q[i+]].x-a[q[i]].x)*l2/d;

       p[].y:=a[q[i]].y+(a[q[i+]].y-a[q[i]].y)*l2/d;

      // writeln(p[].x,' ',p[].y);

       p[].x:=p[].x+(a[q[r]].x-p[].x)*l/dis(p[],a[q[r]]);

       p[].y:=p[].y+(a[q[r]].y-p[].y)*l/dis(p[],a[q[r]]);

       p[].x:=p[].x-(p[].x-a[q[i]].x)*(l2-l1)/dis(p[],a[q[i]]);

       p[].y:=p[].y-(p[].y-a[q[i]].y)*(l2-l1)/dis(p[],a[q[i]]);

       p[].x:=p[].x-(p[].x-p[].x);

       p[].y:=p[].y-(p[].y-p[].y);

     end;

   end;

   writeln(ans::);

   h:=;

   for i:= to  do

     if cmp(p[i],p[h]) then h:=i;

   for i:= to  do

     writeln(p[(h+i) mod ].x::,' ',p[(h+i) mod ].y::);

 end.