题目链接:Beauty Contest
题意:给n个点,求两个点的最远距离。
题解:最长的边肯定是凸多边形的对角线,所以求出凸包后遍历对角线,求出最大距离。
代码:
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include <queue> #include <stack> #include <vector> #include <deque> #include <set> #include <map> #include <string> using namespace std; #define For(i,a) for(i=0;i<a;i++) #define Foru(i,a,b) for(i=a;i<=b;i++) #define Ford(i,a,b) for(i=a;i>=b;i--) #define clr(ar,vel) memset(ar,vel,sizeof(ar)) #define PB push_back typedef long long ll; const int maxint = 0x7fffffff; const ll maxll = 1LL<<60; const double EPS = 1e-10; typedef pair <int,int> pii; // 二维向量类 double add( double a, double b){ if( abs(a+b) < EPS * ( abs(a) + abs(b))) return 0; return a+b; } struct P{ double x, y; P() {} P(double x, double y) : x(x), y(y) {} P operator + (P p){ return P(add(x, p.x), add(y, p.y));} P operator - (P p){ return P(add(x, -p.x), add(y, -p.y));} P operator * (double d){ return P(x*d, y*d);} bool operator < (const P& a) const { if( x != a.x) return x < a.x; else return y < a.y; } double dot(P p){ return add(x*p.x, y*p.y);} double det(P p) { return add( x*p.y, -y*p.x);} }; P p[50010]; int n; bool cmp_x(P a, P b){ if( a.x != b.x) return a.x < b.x; return a.y < b.y; } vector<P> convex_hull(P *ps, int n){ sort(p, p+n, cmp_x); int k = 0; vector<P> qs(n*2); // down for(int i = 0; i < n; i ++){ while( k > 1 && (qs[k-1] - qs[k-2]).det(ps[i] - qs[k-1]) <= 0) k--; qs[k++] = ps[i]; } // up for(int i = n-2, t = k; i >= 0; i --){ while( k > t && (qs[k-1] - qs[k-2]).det(ps[i] - qs[k-1]) <= 0) k--; qs[k++] = ps[i]; } qs.resize(k-1); return qs; } double dist(P p, P q){ return (p-q).dot(p-q); } void solve(){ int x, y; for(int i = 0; i < n; i ++){ scanf("%d%d",&x,&y); // cin >> p[i].x >> p[i].y; p[i].x = x; p[i].y = y; } vector<P> qs = convex_hull(p, n); double res = 0; for(int i = 0; i < qs.size(); i ++){ for(int j = 0; j < i; j ++){ res = max( res, dist(qs[i], qs[j])); } } printf("%.0f\n",res); } int main(){ while(~scanf("%d",&n)) solve(); return 0; }