51nod 1278 相离的圆(排序）

分析：定义两个数组l和r，分别用来存储圆的左边界与x轴交点和圆的右边界与x轴交点，并升序排列。

　　　然后枚举r数组中的点，通过二分法（STL）找到在l数组中第一个比r[i]大的元素的位置，累加（n-pos)即可。

代码：

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 typedef long long ll;
 5 ll n;
 6 ll l[50005];
 7 ll r[50005];
 8 int main()
 9 {
10     ios::sync_with_stdio(false);
11     cin>>n;
12     for(ll i=0;i<n;i++)
13     {
14         int tmp;
15         cin>>l[i];
16         cin>>tmp;
17         r[i]=l[i];
18         l[i]-=tmp;
19         r[i]+=tmp;
20     }
21     sort(l,l+n);
22     sort(r,r+n);
23     ll ans=0;
24     for(ll i=0;i<n;i++)
25     {
26         ll pos=upper_bound(l,l+n,r[i])-l;
27         if(pos==n)
28             break;
29         ans+=(n-pos);
30     }
31     cout<<ans<<endl;
32     return 0;
33 }

View Code

1278 相离的圆

基准时间限制：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示例

Output示例