本文主要是介绍51Nod_1278 相离的圆【贪心+二分】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
51Nod_1278 相离的圆
http://www.51nod.com/Challenge/Problem.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}是相离的。
输入
第1行：一个数N，表示圆的数量(1 <= N <= 50000)；第2 - N + 1行：每行2个数P, R中间用空格分隔，P表示圆心的位置，R表示圆的半径(1 <= P, R <= 10^9)
输出
输出共有多少对相离的圆。
样例输入
4
1 1
2 1
3 2
4 1样例输出
1分析
将圆看作一条在X轴上的线段，左右端点的坐标为圆心坐标减、加半径。然后将线段进行排序，左端点小的排在前面，左端点相同时右端点小的排在前面 ，然后遍历n个圆，统计与此时遍历的圆相离的圆的个数，找到第一个与圆i相离的圆的编号，由排序原则可知，此圆之后的圆都与圆i相离，使用二分法查找与圆i相离的第一个圆的编号，具体看程序。
C++程序
#include<iostream>
#include<algorithm>using namespace std;const int N=50100;typedef long long ll;struct Line{int l,r;//左右端点的一维坐标 bool operator <(const Line &p)const{//左端点小的排在前面，左端点相同时右端点小的排在前面 return l==p.l?(r<p.r):(l<p.l);}
}a[N];int main()
{int n,x,r;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d%d",&x,&r);a[i].l=x-r;a[i].r=x+r;}sort(a,a+n);ll ans=0;for(int i=0;i<n;i++)//统计与圆i相离的圆的个数{//找到第一个与圆i相离(a[id].l>a[i].r)的圆的编号，由排序原则可知，此圆之后的圆都与圆i相离//使用二分查找 int l=i+1,r=n-1,mid=n;while(l<=r){mid=(l+r)/2;if(a[mid].l<a[i].r)l=mid+1;else if(a[mid].l>a[i].r)r=mid-1;else break;}while(mid<n&&a[mid].l<=a[i].r) mid++; //记录第一个与圆i相离的圆的编号 if(mid!=n)ans+=n-mid; } printf("%lld\n",ans);return 0;
}
这篇关于51Nod_1278 相离的圆【贪心+二分】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
