51Nod 1278 相离的圆
Link： http://www.51nod.com/onlineJudge/questionCode.html#!problemId=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
题解：
复杂度 O(nlogn)
因为圆在x轴上， 将圆转换为 两点pair 进行 快排序 之后， 进行搜索找相离的圆的个数。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 500000 + 5; struct Node{
int r, l;
}nd[maxn]; int n; int cmp(const void *a, const void *b){
Node *aa = (Node *)a;
Node *bb = (Node *)b;
return aa->l - bb->l;
} int find(int a, int b, int val){
int mid, left = a, right = b;
while(left < right){
mid = left + (right - left)/2;
if(nd[mid].l > val){
right = mid;
}else{
left = mid + 1;
}
}
return left;
} int main(){
/// freopen("in.txt", "r", stdin); int x, y, p, ans;
while(scanf("%d", &n) != EOF){
for(int i=0; i<n; ++i){
scanf("%d %d", &x, &y);
nd[i].l = x - y;
nd[i].r = x + y;
}
qsort(nd, n, sizeof(nd[0]), cmp);
ans = 0;
for(int i=0; i<n-1; ++i){
p = find(i+1, n, nd[i].r);
ans += n - p;
}
printf("%d\n", ans);
}
return 0;
}