51NOD 1278 相离的圆(二分 + 排序)

相离的圆(二分 + 排序)"/>

51NOD 1278 相离的圆(二分 + 排序)

传送门

平面上有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

解题思路：
因为他们都是在 X 轴上，所以我们可以将其转为线段相交，因为要求的是圆相离的情况也就是转化后的线段不相交的情况，我们可以将线段的终点按升序排列，如果终点相等的话按起点升序，然后二分查找每一个起点，找到终点大于起点的下标，每次sum+=下标就行了。

My Code：

#include <iostream>
#include <algorithm>using namespace std;
const int MAXN = 100000+5;
struct node
{int left, right, flag;
}a[MAXN];
inline bool cmp(node a, node b)
{if(a.right != a.right)return a.left < b.left;return a.right < b.right;
}
int Binary_search(int l, int r, int x)
{int mid;while(l < r){mid = (l+r)>>1;if(a[mid].right >= x)r = mid-1;elsel = mid+1;}while(l>0 && a[l].right>=x)l--;return l;
}int main()
{int n;while(cin>>n){int c, r, cnt = 0;for(int i=1; i<=n; i++){cin>>c>>r;a[i].left = c-r;a[i].right = c+r;}sort(a+1, a+n+1, cmp);a[0].left = a[0].right = -1;int ans = 0;for(int i=1; i<=n; i++)ans += Binary_search(1, i, a[i].left);cout<<ans<<endl;}return 0;
}