【51Nod】1278 - 相离的圆（二分）

#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(a,b) memset(a,b,sizeof(a))
#define PI acos(-1.0)
#define LL long long
struct node
{
    LL st,endd;
}data[50000+5];
int n;

bool cmp(node a,node b)
{
    if (a.st == b.st)
        return a.endd < b.endd;
    return a.st < b.st;
}

int bin1_f1(int x)      //找到第一个内含圆 
{
    int l = x+1;
    int r = n-1;
    int mid;
    while (r >= l)
    {
        mid = (l + r) >> 1;
        if (data[mid].st == data[x].st)
            l = mid + 1;
        else if (data[mid].endd >= data[x].endd)
            r = mid - 1;
        else
            r = mid - 1;
    }
    if (data[l].st > data[x].st && data[l].endd < data[x].endd)
        return l;       //有满足条件的 
    else
        return n;       //没有满足条件的 
}
int bin1_f2(int x)      //找到最后一个内含圆 
{
    int l = x+1;
    int r = n-1;
    int mid;
    while (r >= l)
    {
        mid = (l + r) >> 1;
        if (data[mid].st == data[x].st)
            l = mid + 1;
        else if (data[mid].endd < data[x].endd)
            l = mid + 1;
        else
            r = mid - 1;
    }
    if (data[l].st > data[x].st && data[l].endd < data[x].endd)
        return l;       //有满足条件的 
    else
        return n-1;     //没有满足条件的 
}
int bin1(int x)     //内含圆的个数 
{
    return bin1_f2(x) - bin1_f1(x) + 1;
}

int bin2(int x)
{
    int l = x + 1;
    int r = n-1;
    int mid;
    while (r >= l)
    {
        mid = (l + r) >> 1;
        if (data[mid].st <= data[x].endd)
            l = mid + 1;
        else
            r = mid - 1;
    }
    return n - l;
}
int main()
{
    scanf ("%d",&n);
    LL O,R;
    for (int i = 0 ; i < n ; i++)
    {
        scanf ("%lld %lld",&O,&R);
        data[i].st = O - R;
        data[i].endd = O + R;
    }
    sort(data,data+n,cmp);
    int ans = 0;
    for (int i = 0 ; i < n-1 ; i++)
    {
//      ans += bin1(i);     //找到内离的圆的个数 （出题的问题了，居然内离不算分离） 
//      printf ("===%d===%d===\n",i,ans);
        ans += bin2(i);     //找到外离的圆的个数 
//      printf ("===%d===%d===\n",i,ans);
    }
    printf ("%d\n",ans);
    return 0;
}