# Poj Solution 2187

```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;
}

```
This entry was posted in poj. Bookmark the permalink.