题意：n个平行于坐标轴的正方形，求出最远点对的平方
题解：首先求出凸包，可以证明最远点对一定是凸包上的点对，接着可以证明最远点对（每个点的对踵点）一定只有3*n/2对
接着使用旋转卡壳找到最远点对，但是白书上的算法过于麻烦
所以我看到一个简单想法就是：
可以直接枚举每个点，接着枚举这个点对应最远的点（三角形面积最大）
这儿对踵点满足一个单峰性质，所以可以使用类似双指针方式维护
//n个平行于坐标轴的正方形，求出最远点对的平方
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define eps 1e-8
#define sgn(x) (x<-eps? -1 : x<eps? 0:1)
#define zero(x) (((x)>0?(x) : -(x))<eps)
const int Max=5e5+;
struct Point
{
double x,y;
Point(double x=,double y=):x(x),y(y) {}
inline Point operator-(const Point& a)const
{
return Point(x-a.x,y-a.y);
}
inline bool operator<(const Point& a)const
{
return sgn(x-a.x)<||zero(x-a.x)&&sgn(y-a.y)<;
}
inline bool operator!=(const Point& a)const
{
return !(zero(x-a.x)&&zero(y-a.y));
}
};
typedef Point Vector;
double Cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
}
double Dis(Point A,Point B)
{
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
int ConvexHull(Point* p,int n,Point* convex)
{
sort(p,p+n);
int m=,k=;
for(int i=; i<n; ++i)
{
if(p[k-]!=p[i])
{
p[k++]=p[i];
}
}
n=k;
for(int i=; i<n; ++i)
{
while(m>&&Cross(convex[m-]-convex[m-],p[i]-convex[m-])<)
m--;
convex[m++]=p[i];
}
k=m;
for(int i=n-; i>=; --i)
{
while(m>k&&Cross(convex[m-]-convex[m-],p[i]-convex[m-])<)
m--;
convex[m++]=p[i];
}
if(n>)
m--;
return m;
}
double RotateStuck(Point* convex,int n)//旋转卡壳(前提:一个凸包),注意凸包去重点不要三点共线
{
double ans=;
int q=;
convex[n]=convex[];//避免取模
for(int p=; p<n; ++p)//枚举一条边
{
while(Cross(convex[p+]-convex[p],convex[q+]-convex[p])>//这儿用的是三角形面积的比较
Cross(convex[p+]-convex[p],convex[q]-convex[p]))//找到对应p这条个点的最远点（由于单峰函数，所以结果类似双指针）
q=(q+)%n;
ans=max(ans,max(Dis(convex[p],convex[q]),Dis(convex[p+],convex[q+])));
}
return ans;
}
Point poi[Max],convex[Max];
double Solve(int n)//求出最远点对的平方
{
double fpp=;
int m=ConvexHull(poi,n,convex);//先找凸包
fpp=RotateStuck(convex,m);//旋转卡壳求对踵点（可以求出凸包上的最远点对）
return fpp*fpp;
}
int main()
{
int t,n;
double w,x,y;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=; i<n; ++i)
{
scanf("%lf%lf%lf",&x,&y,&w);
poi[*i]=Point(x,y);
poi[*i+]=Point(x+w,y);
poi[*i+]=Point(x,y+w);
poi[*i+]=Point(x+w,y+w);
}
printf("%.0f\n",Solve(*n));
}
return ;
}