题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1278 题意：一排圆的圆心在X轴上，给定半径和圆的坐标，求相离的圆的对数。 思路：转换成区间之间不相交问题，先计算出有多少线段是相交的，然后用总数减去就是答案。
#include<cstdio> #include<queue> #include<iostream> #include<vector> #include<map> #include<cstring> #include<string> #include<set> #include<stack> #include<algorithm> #define cle(a) memset(a,0,sizeof(a)) #define inf(a) memset(a,0x3f,sizeof(a)) #define ll long long #define Rep(i,a,n) for(int i=a;i<=n;i++) using namespace std; const int INF = ( 2e9 ) + 2; const int maxn = 5e4+10; struct P { int l,f; }; vector<P> v; bool cmp(P a,P b) { if(a.l!=b.l) return a.l<b.l; else return a.f>b.f; } int main() { int n; scanf("%d",&n); for(int i=0;i<n;i++) { int p,r; scanf("%d%d",&p,&r); v.push_back(P{p-r,1}); v.push_back(P{p+r,-1}); } sort(v.begin(),v.end(),cmp); int cnt=0; ll ans=0; for(int i=0;i<v.size();i++) { if(v[i].f==1) { cnt++; ans=ans+(cnt-1); } else if(v[i].f==-1) { cnt--; } } ans=1LL*(n-1)*n/2 - ans; printf("%lld\n",ans); }发现网上很多都是二分写法：
#include<cstdio> #include<queue> #include<iostream> #include<vector> #include<map> #include<cstring> #include<string> #include<set> #include<stack> #include<algorithm> #define cle(a) memset(a,0,sizeof(a)) #define inf(a) memset(a,0x3f,sizeof(a)) #define ll long long #define Rep(i,a,n) for(int i=a;i<=n;i++) using namespace std; const int INF = ( 2e9 ) + 2; //const int maxn = struct P { int l,r; }; vector<P> v; bool cmp(P a,P b) { if(a.l!=b.l) return a.l<b.l; } int BS(int l,int r,int t) // 找第一个大于等于t的值的下标 { while(l<r) { int mid=(l+r)>>1; if(v[mid].l<=t) l=mid+1; else r=mid; } return l; } int main() { int n; scanf("%d",&n); for(int i=0;i<n;i++) { int p,r; scanf("%d%d",&p,&r); v.push_back(P{p-r,p+r}); } sort(v.begin(),v.end(),cmp); int ans=0; for(int i=0;i<v.size();i++) { int cnt=BS(0,v.size(),v[i].r); ans+=v.size()-cnt; } printf("%d\n",ans); }