POJ 2187 Beauty Contest (凸包)

本文主要是介绍POJ 2187 Beauty Contest (凸包)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目地址：POJ 2187

凸包第一发。。用的大白书上的andew算法。

先求出凸包，然后最大距离一定是凸包之中的某两点之间的距离，然后枚举找出最大值。

代码如下：

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm>using namespace std;
#define LL long long
const int INF=0x3f3f3f3f;
int top, n;
struct Point
{int x, y;
}p[100000], tu[100000];
int dist(Point x, Point y)
{return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y);
}
Point operator - (Point x, Point y)
{Point z;z.x=x.x-y.x;z.y=x.y-y.y;return z;
}
int Cross(Point x, Point y)
{return x.x*y.y-x.y*y.x;
}
int cmp(Point x, Point y)
{if(x.x==y.x) return x.y<y.y;return x.x<y.x;
}
int Max(int x, int y)
{return x>y?x:y;
}
void Andew()
{int i, j, k;sort(p,p+n,cmp);top=0;for(i=0;i<n;i++){while(top>1&&Cross(tu[top-1]-tu[top-2],p[i]-tu[top-1])<=0) top--;tu[top++]=p[i];}k=top;for(i=n-2;i>=0;i--){while(top>k&&Cross(tu[top-1]-tu[top-2],p[i]-tu[top-1])<=0) top--;tu[top++]=p[i];}int max1=-1;for(i=0;i<top;i++){for(j=0;j<i;j++){max1=Max(max1,dist(tu[i],tu[j]));}}printf("%d\n",max1);
}
int main()
{int i;scanf("%d",&n);for(i=0;i<n;i++){scanf("%d%d",&p[i].x,&p[i].y);}Andew();return 0;
}

这篇关于POJ 2187 Beauty Contest (凸包)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---