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}是相离的。

 收起

输入

第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

分析：

一开始想到离散化+树状数组上去了，结果发现自己写错了。

回来先想到了排序，后来自然想到了二分（虽然有学长说这题是排序+二分的原因）

我们先把圆心和半径转化为线段的起始坐标，我们知道只要一条线段的右端点比某线段左端小，则这两条线段一定相离，所以我们先对右端点排序，枚举每一个左端点i，然后二分查找<i的个数即可。

#include<bits/stdc++.h>
using namespace std;

 
struct node
{
  long long l,r;
}a[50005];
long long st[50005],en[50005];
bool cmp(node x,node y)
{
  if(x.l==y.l)
    return x.r<y.r;
  else
    return x.l<y.l;
}

int main()
{
  int n;
  while(~scanf("%d",&n))
  {
    
    long long  pos,d;
    for(int i=1;i<=n;i++)
    {
      scanf("%lld%lld",&pos,&d);
      a[i].l=pos-d;
      a[i].r=pos+d;
      
    }
    //sort(a+1,a+n+1,cmp);
    for(int i=0;i<n;i++)
    {
      st[i]=a[i+1].l;
      en[i]=a[i+1].r;
      //cout<<en[i]<<endl;
      //cout<<a[i+1].l<<"      "<<a[i+1].r<<endl;
    }
    sort(en,en+n);
    long long ans=0;
    for(int i=0;i<n;i++)
    {
      int temp=(lower_bound(en,en+n,st[i])-(en));
      //cout<<st[i]<<" "<<temp<<endl;
      ans+=temp;
      
    }
    printf("%lld\n",ans);
    
  }
  return 0;
}