Beauty Contest

8660 ワード

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=28417#problem/F
n個の点をあげて、集まって最も遠い距離の平方を求めます
集団構想:まずすべての点を囲む凸包を求め、それから暴力列挙して解く(直接暴力はタイムアウトする)

#include<iostream>

#include<cmath>

#include<string.h>

#include<string>

#include<stdio.h>

#include<algorithm>

#include<iomanip>



using namespace std;

#define eps 0.0000000001

#define PI acos(-1.0)



//*******************************************************************************

//    

struct Point{

    double x,y;

    Point(double x=0,double y=0):x(x),y(y){}

};

typedef Point Vector;

Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}

bool operator<(const Vector& a,const Vector& b){return a.x<b.x||(a.x==b.x && a.y<b.y);}

int dcmp(double x){

    if(fabs(x)<eps)return 0;

    else return x<0 ? -1:1;

}

double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}//    

double Length(Vector A){return sqrt(Dot(A,A));}//    

double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}

//********************************************************************************

//         p,  n,     ch,       

////              ,   <=  <

//      ,   dcmp  

//     Andrew  -->1、   2、               

//3、                   ,            ,       

int ConVexHull(Point* p,int n,Point*ch){

    sort(p,p+n);

    int m=0;

    for(int i=0;i<n;i++){//   

        while(m>1 && Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;

        ch[m++]=p[i];

    }

    int k=m;

    for(int i=n-2;i>=0;i--){//   

        while(m>k && Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--;

        ch[m++]=p[i];

    }

    if(n>1)m--;

    return m;

}

//*******************************************************************

Point x[50005];

Point ch[50005];

int main(){

    for(int n;cin>>n&&n;){

        for(int i=0;i<n;i++)cin>>x[i].x>>x[i].y;

        sort(x,x+n);

        int m=ConVexHull(x,n,ch);

        double maxx=-1,anss;

        for(int i=0;i<m;i++){

            for(int j=0;j<m;j++){

                anss=(ch[i].x-ch[j].x)*(ch[i].x-ch[j].x)+(ch[i].y-ch[j].y)*(ch[i].y-ch[j].y);

                if(anss>maxx)maxx=anss;

            }

        }

        cout<<(int)maxx<<'
'; }return 0; }

View Code