Đề 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.