基准时间限制：1 秒 空间限制：131072 KB 分值: 10 难度：2级算法题
收藏
关注平面上有N个圆，他们的圆心都在X轴上，给出所有圆的圆心和半径，求有多少对圆是相离的。
例如：4个圆分别位于1, 2, 3, 4的位置，半径分别为1, 1, 2, 1，那么{1, 2}, {1, 3} {2, 3} {2, 4} {3, 4}这5对都有交点，只有{1, 4}是相离的。
Input
第1行：一个数N，表示圆的数量(1 <= N <= 50000) 第2 - N + 1行：每行2个数P, R中间用空格分隔，P表示圆心的位置，R表示圆的半径(1 <= P, R <= 10^9)
Output
输出共有多少对相离的圆。
Input示例
4 1 1 2 1 3 2 4 1
Output示例
1
分析：
只需要存储两类点，类型为0代表圆与x轴的左交点，类型为1代表圆与x轴的右交点。
将这些点排序，依次从前往后扫一遍，将每个右交点右边剩下的左交点数量累加起来即可。
#include<bits/stdc++.h>
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<math.h>
#include<queue>
#include<set>
#include<map>
#include<iomanip>
#include<algorithm>
#include<stack>
using namespace std;
#define inf 0x3f3f3f3f
typedef long long ll;
struct point
{
int x;
bool type;
bool operator<(point &p2)
{
if(x!=p2.x)return x<p2.x;
else{
return !type;
}
}
} pt[100010];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif // ONLINE_JUDGE
int n;
scanf("%d",&n);
int p,r;
int cnt=0;
int n2=n;
while(n2--)
{
scanf("%d%d",&p,&r);
pt[cnt].x=p-r;pt[cnt++].type=0;
pt[cnt].x=p+r;pt[cnt++].type=1;
}
sort(pt,pt+cnt);
int sum0=n;//剩余的左交点数量
ll ans=0;
for(int i=0;i<cnt;i++)
{
if(!pt[i].type)sum0--;
else ans+=sum0;
}
printf("%lld
",ans);
return 0;
}