根据凸包的单峰性质，穷举第一个顶点
然后先更新第三个顶点，再更新第二个顶点
1 var x,y,q:array[0..50010] of longint; 2 ans,n,t,k,i,j:longint; 3 4 function cross(i,j,k:longint):longint; 5 begin 6 exit((x[i]-x[k])*(y[j]-y[k])-(x[j]-x[k])*(y[i]-y[k])); 7 end; 8 9 function max(a,b:longint):longint; 10 begin 11 if a>b then exit(a) else exit(b); 12 end; 13 procedure swap(var a,b:longint); 14 var c:longint; 15 begin 16 c:=a; 17 a:=b; 18 b:=c; 19 end; 20 21 procedure sort(l,r: longint); 22 var i,j,p,q: longint; 23 begin 24 i:=l; 25 j:=r; 26 p:=x[(l+r) shr 1]; 27 q:=y[(l+r) shr 1]; 28 repeat 29 while (x[i]<p) or (x[i]=p) and (y[i]<q) do inc(i); 30 while (p<x[j]) or (p=x[j]) and (q<y[j]) do dec(j); 31 if not(i>j) then 32 begin 33 swap(x[i],x[j]); 34 swap(y[i],y[j]); 35 inc(i); 36 j:=j-1; 37 end; 38 until i>j; 39 if l<j then sort(l,j); 40 if i<r then sort(i,r); 41 end; 42 43 begin 44 readln(n); 45 while n<>-1 do 46 begin 47 for i:=1 to n do 48 readln(x[i],y[i]); 49 sort(1,n); 50 q[1]:=1; 51 t:=1; 52 for i:=2 to n do 53 begin 54 while (t>1) and (cross(q[t],i,q[t-1])<=0) do dec(t); 55 inc(t); 56 q[t]:=i; 57 end; 58 k:=t; 59 for i:=n-1 downto 1 do 60 begin 61 while (t>k) and (cross(q[t],i,q[t-1])<=0) do dec(t); 62 inc(t); 63 q[t]:=i; 64 end; 65 for i:=2 to t-1 do 66 q[t+i-1]:=q[i]; 67 ans:=cross(q[3],q[2],q[1]); 68 j:=2; 69 k:=3; 70 for i:=1 to t-3 do 71 begin 72 k:=max(k,i+2); 73 j:=max(j,i+1); 74 while (k<i+t-2) and (cross(q[j],q[k+1],q[i])>=cross(q[j],q[k],q[i])) do inc(k); 75 ans:=max(ans,cross(q[j],q[k],q[i])); 76 while (j<k) and (cross(q[j+1],q[k],q[i])>=cross(q[j],q[k],q[i])) do inc(j); 77 ans:=max(ans,cross(q[j],q[k],q[i])); 78 end; 79 writeln(ans/2:0:2); 80 readln(n); 81 end; 82 end.