题意:给出一个多边形,求出多边形最远两点距离的平方。
题解:旋转卡壳模板题,先求凸包再用Andrew求最远点对即可。
代码:
Status | Accepted |
---|---|
Time | 219ms |
Memory | 3128kB |
Length | 2774 |
Lang | G++ |
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <vector> #include <algorithm> using namespace std; const double eps=1e-12; const double pi=acos(-1.0); int dcmp(double x){ if(fabs(x)<eps)return 0;else return x<0?-1:1;} struct Point{ int id; double x, y; Point(){} Point(double _x, double _y){x=_x,y=_y;} void input(){scanf("%lf%lf", &x, &y);} void output(){printf("%.2lf %.2lf\n", x, y);} bool operator==(const Point &p)const{return dcmp(x-p.x)==0 && dcmp(y-p.y)==0;} bool operator <(const Point &p)const{return dcmp(x-p.x)==0?dcmp(y-p.y)<0:x<p.x;} double operator ^(const Point &p)const{return x*p.y-y*p.x;} //叉积 double operator *(const Point &p)const{return x*p.x+y*p.y;} //点积 Point operator +(const Point &p)const{return Point(x+p.x, y+p.y);} Point operator -(const Point &p)const{return Point(x-p.x, y-p.y);} Point operator *(const double &k)const{return Point(x*k, y*k);} Point operator /(const double &k)const{return Point(x/k, y/k);} double len(){return sqrt(x*x+y*y);} //长度 double len2(){return x*x+y*y;} //长度的平方 double distance(Point p){return sqrt((x-p.x)*(x-p.x)+(y-p.y)*(y-p.y));} //距离 }; vector<Point> getConvexHull(vector<Point> res){ vector<Point> ans; sort(res.begin(), res.end()); res.erase(unique(res.begin(), res.end()), res.end()); int cnt=0; for(int i=0;i<res.size();i++){ while(cnt>1 && dcmp((ans[cnt-1]-ans[cnt-2])^(res[i]-ans[cnt-2]))<=0)ans.pop_back(),cnt--; ans.push_back(res[i]),cnt++; } int s=cnt; for(int i=int(res.size())-2;i>=0;--i){ while(cnt>s && dcmp((ans[cnt-1]-ans[cnt-2])^(res[i]-ans[cnt-2]))<=0)ans.pop_back(),cnt--; ans.push_back(res[i]),cnt++; } if(cnt>1)ans.pop_back(); return ans; } pair<int, int> getConvexDiameter(vector<Point> res){ pair<int, int> ans; double maxd=0; int j=1, num=res.size(); res.push_back(res[0]); for(int i=0;i<num;i++){ while(dcmp( ((res[i+1]-res[i])^(res[j+1]-res[i])) - ((res[i+1]-res[i])^(res[j]-res[i])) )>0)j=(j+1)%num; double d=res[i].distance(res[j]); if(d>maxd)ans.first=i, ans.second=j,maxd=d; } return ans; } int N, L; int main(){ cin.sync_with_stdio(false); cout.sync_with_stdio(false); while(~scanf("%d", &N)){ vector<Point> res; Point p; for(int i=0;i<N;i++){ scanf("%lf%lf", &p.x, &p.y); p.id=i+1; res.push_back(p); } vector<Point> hull=getConvexHull(res); pair<int, int> ans=getConvexDiameter(hull); int val=(hull[ans.first]-hull[ans.second]).len2(); printf("%d\n", val); } return 0; }