实现功能：求出二维平面内一对散点的凸包（详见Codevs 1298）
很神奇的算法——先将各个点按坐标排序，然后像我们所知的那样一路左转，求出半边的凸包，然后反过来求另一半的凸包
我以前正是因为总抱着想一步到位的想法，所以每次都跪得很惨（HansBug：事实上这次是我这辈子第一次A掉凸包题）
然后别的没了，就是凸包的基本思想
（顺便输出凸包周长C和面积S）
type arr=array[..] of longint;
var
i,j,k,l,m,n,m1,m2:longint;
a:array[..,..] of longint;
b,c,d:arr;ans,are:extended;
procedure swap(var x,y:longint);
var z:longint;
begin
z:=x;x:=y;y:=z;
end;
procedure sort(l,r:longint);
var i,j,x,y:longint;
begin
i:=l;j:=r;x:=a[(l+r) div ,];y:=a[(l+r) div ,];
repeat
while (a[i,]<x) or ((a[i,]=x) and (a[i,]<y)) do inc(i);
while (a[j,]>x) or ((a[j,]=x) and (a[j,]>y)) do dec(j);
if i<=j then
begin
swap(a[i,],a[j,]);
swap(a[i,],a[j,]);
inc(i);dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
function right(x1,y1,x2,y2:longint):boolean;
begin
exit((x1*y2)>(x2*y1));
end;
function trip(x1,y1,x2,y2,x3,y3:longint):boolean;
begin
exit(right(x2-x1,y2-y1,x3-x2,y3-y2));
end;
function check(x,y,z:longint):boolean;
begin
exit(trip(a[x,],a[x,],a[y,],a[y,],a[z,],a[z,]));
end;
procedure doit(var b:arr;var m:longint);
begin
b[]:=d[];b[]:=d[];j:=;
for i:= to n do
begin
while (j>) and not(check(b[j-],b[j],d[i])) do dec(j);
inc(j);b[j]:=d[i];
end;
m:=j;
end;
begin
readln(n);
for i:= to n do readln(a[i,],a[i,]);
sort(,n);j:=;
for i:= to n do //去重
begin
if (a[i,]<>a[j,]) or (a[i,]<>a[j,]) then
begin
inc(j);
a[j,]:=a[i,];a[j,]:=a[i,];
end;
end;
n:=j;
//求凸包
for i:= to n do d[i]:=i;doit(b,m1);
for i:= to n do d[i]:=n+-i;doit(c,m2);
//两个半边整合
for i:= to m1 do d[i]:=b[i];
for i:= to m2 do d[i+m1-]:=c[i];
//开始计算周长+面积
m:=m1+m2-;ans:=;are:=;
for i:= to m do ans:=ans+sqrt(sqr(a[d[i],]-a[d[i+],])+sqr(a[d[i],]-a[d[i+],])); //周长
for i:= to m do are:=are+a[d[i],]*a[d[i+],]-a[d[i],]*a[d[i+],]; //面积
are:=abs(are)/;
writeln('Convex Hull:');
for i:= to m do writeln(a[d[i],],' ',a[d[i],]);
writeln('C = ',ans::);
writeln('S = ',are::);
readln;
end.