51Nod 1278 相离的圆

Problem

平面上有N个圆，他们的圆心都在X轴上，给出所有圆的圆心和半径，求有多少对圆是相离的。

例如：4个圆分别位于1, 2, 3, 4的位置，半径分别为1, 1, 2, 1，那么{1, 2}, {1, 3} {2, 3} {2, 4} {3, 4}这5对都有交点，只有{1, 4}是相离的。

Solution

注意圆心在坐标轴上，之前因为没看到这句话把题跳了。 然后就可以转化为线段，按照左端点排序，i代表线段循环，二分求左端点在第i条线段右端点左边的最后一个线段，他后面的线段就是相离的，加入答案。

Code

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
#define io_opt std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
int n,ans;
struct E{
	int s,t;
}e[50020];
int cmp(E x,E y){
	if(x.s==y.s) return x.t<y.t;
	return x.s<y.s;
}
int main(){
	//io_opt;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int x,r;
		scanf("%d%d",&x,&r);
		e[i].s=x-r;
		e[i].t=x+r;
	}
	sort(e+1,e+1+n,cmp);
	for(int i=1;i<=n;i++){
		int l=i,r=n,mid,tmp=i;
		while(l<=r){
			mid=(l+r)>>1;
			if(e[mid].s<=e[i].t){
				l=mid+1;
				tmp=mid;
			}
			else{
				r=mid-1;
			}
		}
		ans+=n-tmp;
	}
	printf("%d\n",ans);
	return 0;
}