在解题报告之前，首先对同一次作业中另外一题（求逆序对）某人在未经冰少允许情况下，擅自登录冰少账号，原模原样剽窃冰少代码，并且最终还被评为优秀作业的行为表示严正抗议！
题目大意：
二维平面上给出 n 个点。然而再给出两个源点，分别以这两个源点为圆心做两个圆，设半径为 r1,r2。要求n 个点中的每个点都要至少被一个圆包含（在圆周上也算）。在满足要求的条件下，半径平方之和$(r1^2 + r2^2)$越小越好（半径可以是 0）。
对于 100%的数据 1<=N<=100000,且所有点与原点的距离都不超过 1000。
输出只有一个整数，表示最小的半径平方之和$(r1^2 + r2^2)$。
解题思路：
首先解决精度问题，答案要求输入最小半径平方和，因此在求距离直接保留其距离平方即可，不要开根号防止爆精度情况发生。
其次分析题目，易证得，两个圆的半径大小要么为0，要么为该圆心到某个点的距离，因此，我们可以枚举第一个圆的半径大小，覆盖圆的个数，那么剩下的圆显然要被另一个圆覆盖。
对于每个点，我们记录该点其到圆1距离以及圆2的距离，然后对这些点到圆1距离从大到小进行排序，从n至0枚举圆1覆盖的圆的个数，同时，对距离圆2的距离维护前缀最大值，二者相加取min即可。注意，这里从n至0枚举是因为可以实时更新圆2的半径大小，而若从0-n枚举则需要后缀最大值，需要使用dp进行维护，且空间复杂度较高，因此从n-0枚举。
时间复杂度，点排序$O(nlogn)$，半径枚举$O(n)$，总时间复杂度$O(nlogn)$。
具体代码实现如下：
#include<bits/stdc++.h> using namespace std; typedef pair <int,int> pii; #define rep(i,x,y) for(int i=x;i<y;i++) #define rept(i,x,y) for(int i=x;i<=y;i++) #define per(i,x,y) for(int i=x;i>=y;i--) #define pb push_back #define fi first #define se second #define mes(a,b) memset(a,b,sizeof a) #define mp make_pair #define dd(x) cout<<#x<<"="<<x<<" "; #define de(x) cout<<#x<<"="<<x<<" "; int read() { int ans=0; int flag=1; char ch; while( (ch=getchar())<'0' || ch>'9' ) if(ch=='-') flag=-1; while( ch>='0' && ch<='9' ) { ans=ans*10+ch-'0'; ch=getchar(); } return flag*ans; } const int maxn=1e5+5; pii point[maxn]; int d(int x,int y,int ox,int oy) { return (x-ox)*(x-ox)+(y-oy)*(y-oy); } bool comp(const pii &s1,const pii &s2) { return s1.fi>s2.fi; } int main() { int o1x,o2x,o1y,o2y; o1x=read(); o1y=read(); o2x=read(); o2y=read(); int n; n=read(); rep(i,0,n) { int x,y; x=read(); y=read(); point[i].fi=d(x,y,o1x,o1y); point[i].se=d(x,y,o2x,o2y); } sort(point,point+n,comp); int ans=point[0].fi,r2=0; rep(i,0,n) { ans=min(ans,point[i].fi+r2); r2=max(r2,point[i].se); } ans=min(ans,r2); printf("%d ",ans); return 0; }