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