1069: [SCOI2007]最大土地面积

Description

在某块平面土地上有N个点，你可以选择其中的任意四个点，将这片土地围起来，当然，你希望这四个点围成的多边形面积最大。
Input

第1行一个正整数N，接下来N行，每行2个数x,y，表示该点的横坐标和纵坐标。
Output

最大的多边形面积，答案精确到小数点后3位。
Sample Input
5
0 0
1 0
1 1
0 1
0.5 0.5
Sample Output
1.000

HINT

数据范围 n<=2000, |x|,|y|<=100000

先求凸包

然后枚举四边形的对角线，分别找到距离最远的两个点更新答案（这两个点都是单调的），总复杂度是O（n^2）的

哪里写挫了，超慢，总时间1600ms

 const

         maxn=;

 type

         point=record

           x,y:double;

         end;

 var

         a:array[..maxn]of point;

         n:longint;

         min:point;

 function cj(a,b,c:point):double;

 begin

         exit((a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y));

 end;

 procedure swap(var x,y:point);

 var

         t:point;

 begin

         t:=x;x:=y;y:=t;

 end;

 procedure sort(l,r:longint);

 var

         i,j:longint;

         y:point;

 begin

         i:=l;

         j:=r;

         y:=a[(l+r)>>];

         repeat

           while cj(y,a[i],min)< do

             inc(i);

           while cj(y,a[j],min)> do

             dec(j);

           if i<=j then

           begin

             swap(a[i],a[j]);

             inc(i);

             dec(j);

           end;

         until i>j;

         if i<r then sort(i,r);

         if j>l then sort(l,j);

 end;

 procedure init;

 var

         i:longint;

 begin

         read(n);

         min.x:=maxlongint;

         min.y:=maxlongint;

         for i:= to n do

           begin

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

             if (a[i].x<min.x) or ((a[i].x=min.x) and (a[i].y<min.y)) then min:=a[i];

           end;

         i:=n;

         while i> do

           begin

             if (a[i].x=min.x) and (a[i].y=min.y) then

               begin

                 a[i]:=a[n];

                 dec(n);

               end

             else dec(i);

           end;

         sort(,n);

         inc(n);

         a[n]:=min;

         a[]:=min;

 end;

 var

         q:array[..maxn]of longint;

         f:array[..maxn,..]of double;

         tot,lasta,lastb:longint;

         ans:double;

 function up(var x:double;y:double):boolean;

 begin

         if x<y then

         begin

           x:=y;

           exit(true);

         end;

         exit(false);

 end;

 function down(var x:double;y:double):boolean;

 begin

         if x>y then

         begin

           x:=y;

           exit(true);

         end;

         exit(false);

 end;

 procedure work;

 var

         i,j:longint;

 begin

         for i:= to n do

           begin

             while (tot>) and (cj(a[i],a[q[tot]],a[q[tot-]])>=) do

               dec(tot);

             inc(tot);

             q[tot]:=i;

           end;

         for i:= to tot- do

           begin

             f[i+,]:=-maxlongint;

             f[i+,]:=;

             for j:= to n do

               if up(f[i+,],cj(a[q[i+]],a[q[j]],a[q[i]])) then lasta:=j;

             lastb:=i;

             for j:=i+ to tot do

               begin

                 f[j,]:=cj(a[q[j]],a[q[lasta]],a[q[i]]);

                 f[j,]:=cj(a[q[j]],a[q[lastb]],a[q[i]]);

                 while up(f[j,],cj(a[q[j]],a[q[lasta mod tot+]],a[q[i]])) do

                   lasta:=lasta mod tot+;

                 while down(f[j,],cj(a[q[j]],a[q[lastb mod tot+]],a[q[i]])) do

                   lastb:=lastb mod tot+;

                 up(ans,f[j,]-f[j,]);

               end;

           end;

         writeln(ans/::);

 end;

 begin

         init;

         work;

 end.

巴特西

1069: [SCOI2007]最大土地面积 - BZOJ

最新文章

热门文章