http://poj.org/problem?id=2187
#include"stdio.h"
#include"math.h"
#include<vector>
#include<algorithm>
using namespace std;
////////////////////////////////
typedef int Type;/*????????*/
////////////////////////////////
//????????
struct point
{
Type x,y;
point(){x=y=0;}
point(Type x,Type y):x(x),y(y){;}
bool operator==(point &a){return x==a.x&&y==a.y;}
};
//????
inline Type cheng(point a,point b,point c)
{return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}
inline Type cheng(point b,point c)
{return b.x*c.y-c.x*b.y;}
//????
inline Type dcheng(point a,point b,point c)
{return (b.x-a.x)*(c.x-a.x)+(c.y-a.y)*(b.y-a.y);}
inline Type dcheng(point b,point c)
{return b.x*c.x+c.y*b.y;}
//??????????
int dis(point a,point b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int cmp_x_y(point a,point b)
{return a.y<b.y||(a.y==b.y&&a.x<b.x);}
void sort(point *a,int n)
{sort(&a[0],&a[n],cmp_x_y);}
////////////////////////////////////////////////////////////
//O(n*log(n))
//??????,??????????????????????wall:????????????
//security
//p????????????!!!
const long convex_size=50010;
int stack[convex_size],sign[convex_size];
int convex(point *p,int n,point *wall)
{
int i;int st;Type h;
st=0;
stack[st++]=0;
stack[st++]=1;
for(i=0;i<n;i++)sign[i]=0;
sign[1]=1;
i=2;
while(i<n)
{
while(st>=2&&(h=cheng(p[stack[st-1]],p[stack[st-2]],p[i]))/**/ > /**/ 0)
//????????????????use '>'; ??????????????????????||n<3,??????'>'??????????
{
st--;
if(h)sign[stack[st]]=0;
}
stack[st++]=i;sign[i]=1;
i++;
}
i--;
while(i>=0)
{
while(sign[i])i--;
while(st>=2&&cheng(p[stack[st-1]],p[stack[st-2]],p[i])/**/ > /**/ 0)st--;
//????
stack[st++]=i;
i--;
}
st--;
if(wall)
{
for(i=0;i<st;i++)wall[i]=p[stack[i]];
}
return st;
}
///////////////////////////////////////////////////////////////////
point p[50010], pt[50010];
int n;
inline int dis_squr( point &a, point &b )
{
return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}
int main()
{
int i, j;
int temp, best;
point a, b;
scanf( "%d", &n );
for( i=0; i<n; i++ )
scanf("%d %d", &pt[i].x, &pt[i].y );
sort( pt, n );
n = convex( pt, n, p );
best = 0;
for( i=0; i<n; i++ )
for( j=i+1; j<n; j++ )
if( ( temp = dis( p[i], p[j] ) ) > best )
best = temp;
printf( "%dn", best );
return 0;
}