Đề bài: Cho N điểm phân biệt bất kỳ, hãy viết giải thuật tìm ra 4 điểm từ N điểm đã cho mà 4 điểm đó tạo thành 1 tứ giác có diện tích lớn nhất.

Input: 

• Dòng đầu tiên chứa 1 số nguyên N, số lượng điểm trong tập hợp đã cho
• N dòng tiếp theo, mỗi dòng chứa 2 số nguyên cách nhau bằng 1 khoảng trắng là tọa độ xi yi của điểm thứ i trong tập hợp điểm, (không có 2 điểm nào trùng nhau)
• Giới hạn: (4<=N<=106) ; (-106<= xi, yi <=106)

Output: Gồm 1 dòng duy nhất chứa diện tích của tứ giác tìm được.

CODE:

const
        fi='TGIACMAX.INP';
        fo='TGIACMAX.OUT';
type rec = record
        x,y : longint;
        end;
var
        n : longint;
        a : array[1..5000] of rec;
        res,kq,tmp : extended;
        aa,bb,cc : longint;
procedure int;
var i : longint;
begin
        assign(input,fi); reset(input);
        read(n);
        for i :=1 to n do
        begin
                read(a[i].x,a[i].y);
                a[i+n].x := a[i].x;
                a[i+n].y := a[i].y;
        end;
        close(input);
end;
function kc(x : longint) : extended;
var
        TU,MAU : extended;
begin
        TU :=  abs(aa*a[x].x+bb*a[x].y+cc);
        MAU := sqrt(sqr(aa)+sqr(bb));
        exit (tu/mau);
end;
function dd : extended;
begin
        exit(sqrt(sqr(aa)+sqr(bb)));
end;
procedure CNP(l,r : longint);
var
        mid : longint;
        a,b,c : extended;
begin
        if l > r then exit;
        if l = r then
        begin
                if kc(l) > tmp then tmp := kc(l);
                exit;
        end;
        a := kc(l);
        b := kc(r);
        mid := (l+r) div 2;
        c := kc(mid);
        if c > tmp then
        begin
                tmp := kc(mid);
                if kc(mid+1) > c then
                        CNP(mid,r)
                else    CNP(l,mid);
                exit;
        end;
        if a < b then CNP(mid+1,r) else CNP(l,mid-1);
end;

procedure xuli(x,y : longint);
var i,j,u  : longint;
begin
        aa := a[x].y-a[y].y;
        bb := a[y].x-a[x].x;
        cc := - (aa*a[x].x+bb*a[x].y);
        tmp := 0;
        CNP(y+1,x+n-1);
        res := tmp*dd;
        tmp := 0;
        CNP(x+1,y-1);

        res := res + tmp*dd;
end;
function getmax(x,y : extended) : extended;
begin
        if x > y then exit(x) ;
        exit(y);
end;
procedure slove;
var i,j : longint;
begin
        kq := 0;
        for i :=1 to n -1 do
          for j := i +(n div 3)+(n div 7 )to n do
          begin
                xuli(i,j);
                kq := getmax(res,kq);
          end;
          kq := kq/2;
end;
procedure outt;
begin
        assign(output,fo); rewrite(output);
        write(kq:0:1);
        close(output);
end;
BEGIN
        int;
        slove;
        outt;
END.