将圆化成 x 轴上的线段, 每一个线段有左端点和右端点, 按照左端点排序, 左端点相同右端点小的在前, 然后二分查找与当前线段最接近的线段, 得出这是第几个线段, 求和.
- #include <iostream>
- #include <math.h>
- #include <algorithm>
- #include <stdio.h>
- using namespace std;
- struct node{
- int l,r;
- }a[50005];
- bool cmp(node a,node b)
- {
- if(a.l==b.l) return a.r<b.r;
- else return a.l<b.l;
- }
- int find(int left,int right,int e)
- {
- int ll=left,rr=right;
- int mid;
- while(ll<=rr)
- {
- mid=(ll+rr)/2;
- if(a[mid].l<=e) ll=mid+1;
- else rr=mid-1;
- }
- return ll;
- }
- int main()
- {
- int n,c,r;
- cin>>n;
- for(int i=0;i<n;i++)
- {
- cin>>c>>r;
- a[i].l=c-r;
- a[i].r=c+r;
- }
- sort(a,a+n,cmp);
- //for(int i=0;i<n;i++) cout<<a[i].l<<" "<<a[i].r<<endl;
- int ans=0;
- for(int i=0;i<n;i++)
- {
- int j=find(i+1,n-1,a[i].r);//cout<<i<<" "<<j<<endl;
- ans+=(n-j);
- }
- cout<<ans<<endl;
- }
来源: http://www.bubuko.com/infodetail-2582816.html