关键点：每次将不满组条件的两个村民i,j(i<j)标记，这样下次不再计算j村民，节约时间
#include <iostream> #include <cstring> using namespace std; #define MAX 50005 #define INF 1e7 bool vis[MAX]; struct node{ int x,y; }point[MAX]; int main() { int t,n,mi,m,temp,x,y,d;cin>>t; while (t--) { cin>>n; mi=INF; memset(vis,0,sizeof(vis)); for (int i=0;i<n;i++) cin>>point[i].x>>point[i].y; for (int i=0;i<n;i++) { if (!vis[i]) { temp=0; for (int j=0;j<n;j++) { if(j==i) continue; x=point[i].x-point[j].x; y=point[i].y-point[j].y; d=x*x+y*y; if (d>mi) { vis[i]=1; vis[j]=1; break; } if (d>temp) temp=d; } if (!vis[i]&&mi>temp) mi=temp; } } cout<<mi<<endl; } return 0; }