题目地址：https://vjudge.net/problem/UVALive-4728
最远的两点肯定是凸包上的点，所以先求凸包
再枚举凸包上的两个点，更新最远的距离，这里用滑动窗口算法优化
也按照旋转卡壳方法写了一遍
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=(int)(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(int)(b);--i)
const double PI=acos(-1);
const double EPS=1e-6;
int dcmp(double x){if(fabs(x)<EPS) return 0;return x > 0 ? 1 : -1;
}
struct Point{double x,y;
};
typedef Point Vector;
bool operator < (const Point& p1, const Point& p2){ return p1.x<p2.x || (p1.x==p2.x && p1.y<p2.y) ;}
Vector operator / (const Point& A, double x){ return Vector{A.x/x, A.y/x};}
Vector operator * (const Vector& A, double x){ return Vector{A.x*x, A.y*x};}
Vector operator - (const Vector& A, const Vector& B){ return Vector{A.x-B.x,A.y-B.y};}
Vector operator + (const Point& A, const Vector& v){ return Point{A.x+v.x,A.y+v.y};}
Vector Rotate(const Point& p,double ang){ return Vector{p.x*cos(ang)-p.y*sin(ang),p.x*sin(ang)+p.y*cos(ang)};}
double Cross(const Vector& A, const Vector& B){ return A.x*B.y-A.y*B.x;}
double Dot(Vector A, Vector B){ return A.x*B.x+A.y*B.y;}
double LengthSquare(Vector v){ return fabs(Dot(v,v));}const int maxn=100000+5;
Point s[maxn*4],sol[maxn];
double w[maxn];
int convexHull(Point* A, int n, Point* sol){sort(A,A+n);int m=0;REP(i,0,n-1){while(m>1 && dcmp( Cross(sol[m-1]-sol[m-2], A[i]-sol[m-1])) <= 0) m--;sol[m++]=A[i];}int k=m;REPD(i,n-2,0){while(m>k && dcmp( Cross(sol[m-1]-sol[m-2], A[i]-sol[m-1])) <= 0) m--;sol[m++]=A[i];}if(n>1) m--;return m;
}
double RotateCaliper(Point* A, int n){ //旋转卡壳A[n]=A[0];double ans=0.;for(int u=0,v=1;u<n;u++){for(;;){int sign=dcmp( Cross(A[u+1]-A[u], A[v+1]-A[v]));if(sign<=0){ans=max(ans, LengthSquare(A[v]-A[u]));if(sign==0) ans=max(ans, LengthSquare(A[v+1]-A[u]));break;}v=(v+1)%n;}}return ans;
}
int main(int argc, char const *argv[])
{// freopen("input.in","r",stdin);int T,n; scanf("%d",&T);while(T--&&scanf("%d",&n)==1){int pCnt=0;REP(i,0,n-1) {double x,y,w;scanf("%lf%lf%lf",&x,&y,&w);s[pCnt++]=Point{x+w,y};s[pCnt++]=Point{x,y+w};s[pCnt++]=Point{x+w,y+w};s[pCnt++]=Point{x,y};}int cnt=convexHull(s,pCnt,sol);/*int i=0,j=0; double D=0.;while(i<cnt&&j<cnt){while(j<cnt-1 && dcmp(LengthSquare(sol[j+1]-sol[i])-LengthSquare(sol[j]-sol[i])) >0 ) j++;D=max(D,LengthSquare(sol[j]-sol[i]));i++;}printf("%.0lf\n", D);*/printf("%.0lf\n", RotateCaliper(sol,cnt));}return 0;
}