題意：

給出n個點，求最遠的點對的距離的平方。

思路：

旋轉卡殼。

代碼：

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cmath> #include<vector>using namespace std;const double pi=acos(-1.0);const double eps=1e-8;int cmp(double x) {if(fabs(x)<eps)return 0;if(x>0)return 1;return -1; }inline double sqr(double x) {return x*x; }struct point {double x,y;point() {}point(double a,double b):x(a),y(b){}friend point operator + (const point &a,const point &b){return point(a.x+b.x,a.y+b.y);}friend point operator - (const point &a,const point &b){return point(a.x-b.x,a.y-b.y);}friend bool operator == (const point &a,const point &b){return cmp(a.x-b.x)==0&&cmp(a.y-b.y)==0;}friend point operator * (const point &a,const double &b){return point(a.x*b,a.y*b);}friend point operator * (const double &a,const point &b){return point(a*b.x,a*b.y);}friend point operator / (const point &a,const double &b){return point(a.x/b,a.y/b);}double norm(){return sqrt(sqr(x)+sqr(y));} };double det(const point &a,const point &b)//cha {return a.x*b.y-a.y*b.x; } double dot(const point &a,const point &b) {return a.x*b.x+a.y*b.y; } double dist(const point &a,const point &b) {return (a-b).norm(); } point rotate_point(const point &p,double A)//ni {double tx=p.x,ty=p.y;return point(tx*cos(A)-ty*sin(A),tx*sin(A)+ty*cos(A)); }struct polygon_convex {vector<point> P;polygon_convex(int Size=0){P.resize(Size);} };bool cmp_less(const point &a,const point &b) {return cmp(a.x-b.x)<0||cmp(a.x-b.x)==0&&cmp(a.y-b.y)<0; }polygon_convex convex_hull(vector<point> a) {polygon_convex res(2*a.size()+5);sort(a.begin(),a.end(),cmp_less);a.erase(unique(a.begin(),a.end()),a.end());int m=0;for(int i=0;i<a.size();i++){while(m>1 && cmp(det(res.P[m-1]-res.P[m-2],a[i]-res.P[m-2]))<=0)--m;res.P[m++]=a[i];}int k=m;for(int i=int(a.size())-2;i>=0;i--){while(m>k && cmp(det(res.P[m-1]-res.P[m-2],a[i]-res.P[m-2]))<=0)--m;res.P[m++]=a[i];}res.P.resize(m);if(a.size()>1)res.P.resize(m-1);return res; }double convex_diameter(polygon_convex &a,int &First,int &Second) {vector<point> &p=a.P;int n=p.size();double maxd=0.0;if(n==1){First=Second=0;return maxd;}#define next(i) ((i+1)%n)for(int i=0,j=1;i<n;i++){while(cmp(det(p[next(i)]-p[i],p[j]-p[i])-det(p[next(i)]-p[i],p[next(j)]-p[i]))<0){j=next(j);}double d=dist(p[i],p[j]);if(d>maxd){maxd=d;First=i,Second=j;}d=dist(p[next(i)],p[next(j)]);if(d>maxd){maxd=d;First=i,Second=j;}}return maxd; }vector<point> tt; int main() {int n;while(scanf("%d",&n)!=EOF){tt.clear();for(int i=0;i<n;i++){double tx,ty;scanf("%lf%lf",&tx,&ty);tt.push_back(point(tx,ty));}polygon_convex xx=convex_hull(tt);int ans1,ans2;double ans=convex_diameter(xx,ans1,ans2);printf("%.0lf\n",ans*ans);}return 0; }

總結

以上是生活随笔為你收集整理的poj2187(最远点的距离的平方)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。