求N个点中的任意两点的最大距离，先求凸包O(nlgn)，再用旋转卡壳O(n)，可惜的是，我现在还不会旋转卡壳，先发个枚举的代码，O(n2)的……也能过~~
#include <iostream>
#include <cmath>
using namespace std;
#define eps 1e-8
struct Point{int x,y;};
Point org[50001], stk[50001];
//计算cross product (P1-P0)x(P2-P0)
int Xmult(Point p1,Point p2,Point p0){
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
//Graham_Scan算法顺时针构造包含所有共线点的凸包,O(nlogn)
Point p1,p2;
int graham_cp(const void* a,const void* b){
int ret=Xmult(*((Point*)a),*((Point*)b),p1);
return (ret==0)?(Xmult(*((Point*)a),*((Point*)b),p2)>0?1:-1):(ret>0?1:-1);
}
void _graham(int n,Point* pt,int& s,Point* ch){
int i,k=0;
for (p1=p2=pt[0],i=1;i<n;p2.x+=pt[i].x,p2.y+=pt[i].y,i++)
if (p1.y-pt[i].y>eps||((p1.y-pt[i].y==0)&&p1.x>pt[i].x))
p1=pt[k=i];
p2.x/=n,p2.y/=n;
pt[k]=pt[0],pt[0]=p1;
qsort(pt+1,n-1,sizeof(Point),graham_cp);
for (ch[0]=pt[0],ch[1]=pt[1],ch[2]=pt[2],s=i=3;i<n;ch[s++]=pt[i++])
for (;s>2&&Xmult(ch[s-2],pt[i],ch[s-1])<-eps;s--);
}
//原始点集pt，凸包点集convex，返回凸包点集大小
int Graham_Scan(int n,Point* pt,Point* convex,int iscollinear=1,int isclockwise=1){
Point* temp=new Point[n];
int s,i;
_graham(n,pt,s,temp);
for (convex[0]=temp[0],n=1,i=(isclockwise?1:(s-1));isclockwise?(i<s):i;i+=(isclockwise?1:-1))
if (iscollinear||Xmult(temp[i-1],temp[i],temp[(i+1)%s])!=0)
convex[n++]=temp[i];
delete []temp;
return n;
}
int main(){
int n, i, j, max= 0, tmp;
scanf("%d",&n);
for( i= 0; i< n; i++ )
scanf("%d%d",&org[i].x,&org[i].y);
n= Graham_Scan(n,org,stk);
for( i= 0; i< n; i++ )
for( j= i+1; j< n; j++ ){
tmp= (stk[i].x-stk[j].x)*(stk[i].x-stk[j].x)+(stk[i].y-stk[j].y)*(stk[i].y-stk[j].y);
if( tmp> max ) max= tmp;
}
printf("%d\n",max);
return 0;
}posted on 2009-06-26 21:09
古月残辉 阅读(396)
评论(0) 编辑 收藏 引用 所属分类:
计算几何