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

  1 const
  2         maxn=2010;
  3 type
  4         point=record
  5           x,y:double;
  6         end;
  7 var
  8         a:array[0..maxn]of point;
  9         n:longint;
 10         min:point;
 11  
 12 function cj(a,b,c:point):double;
 13 begin
 14         exit((a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y));
 15 end;
 16  
 17 procedure swap(var x,y:point);
 18 var
 19         t:point;
 20 begin
 21         t:=x;x:=y;y:=t;
 22 end;
 23  
 24 procedure sort(l,r:longint);
 25 var
 26         i,j:longint;
 27         y:point;
 28 begin
 29         i:=l;
 30         j:=r;
 31         y:=a[(l+r)>>1];
 32         repeat
 33           while cj(y,a[i],min)<0 do
 34             inc(i);
 35           while cj(y,a[j],min)>0 do
 36             dec(j);
 37           if i<=j then
 38           begin
 39             swap(a[i],a[j]);
 40             inc(i);
 41             dec(j);
 42           end;
 43         until i>j;
 44         if i<r then sort(i,r);
 45         if j>l then sort(l,j);
 46 end;
 47  
 48 procedure init;
 49 var
 50         i:longint;
 51 begin
 52         read(n);
 53         min.x:=maxlongint;
 54         min.y:=maxlongint;
 55         for i:=1 to n do
 56           begin
 57             read(a[i].x,a[i].y);
 58             if (a[i].x<min.x) or ((a[i].x=min.x) and (a[i].y<min.y)) then min:=a[i];
 59           end;
 60         i:=n;
 61         while i>0 do
 62           begin
 63             if (a[i].x=min.x) and (a[i].y=min.y) then
 64               begin
 65                 a[i]:=a[n];
 66                 dec(n);
 67               end
 68             else dec(i);
 69           end;
 70         sort(1,n);
 71         inc(n);
 72         a[n]:=min;
 73         a[0]:=min;
 74 end;
 75  
 76 var
 77         q:array[0..maxn]of longint;
 78         f:array[0..maxn,0..1]of double;
 79         tot,lasta,lastb:longint;
 80         ans:double;
 81  
 82 function up(var x:double;y:double):boolean;
 83 begin
 84         if x<y then
 85         begin
 86           x:=y;
 87           exit(true);
 88         end;
 89         exit(false);
 90 end;
 91  
 92 function down(var x:double;y:double):boolean;
 93 begin
 94         if x>y then
 95         begin
 96           x:=y;
 97           exit(true);
 98         end;
 99         exit(false);
100 end;
101  
102 procedure work;
103 var
104         i,j:longint;
105 begin
106         for i:=1 to n do
107           begin
108             while (tot>0) and (cj(a[i],a[q[tot]],a[q[tot-1]])>=0) do
109               dec(tot);
110             inc(tot);
111             q[tot]:=i;
112           end;
113         for i:=1 to tot-1 do
114           begin
115             f[i+1,1]:=-maxlongint;
116             f[i+1,0]:=0;
117             for j:=1 to n do
118               if up(f[i+1,1],cj(a[q[i+1]],a[q[j]],a[q[i]])) then lasta:=j;
119             lastb:=i;
120             for j:=i+2 to tot do
121               begin
122                 f[j,1]:=cj(a[q[j]],a[q[lasta]],a[q[i]]);
123                 f[j,0]:=cj(a[q[j]],a[q[lastb]],a[q[i]]);
124                 while up(f[j,1],cj(a[q[j]],a[q[lasta mod tot+1]],a[q[i]])) do
125                   lasta:=lasta mod tot+1;
126                 while down(f[j,0],cj(a[q[j]],a[q[lastb mod tot+1]],a[q[i]])) do
127                   lastb:=lastb mod tot+1;
128                 up(ans,f[j,1]-f[j,0]);
129               end;
130           end;
131         writeln(ans/2:0:3);
132 end;
133  
134 begin
135         init;
136         work;
137 end.

View Code