題目

平面上有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 軸上，因此可以將相離問題轉化為線段相交問題。

由于求的是圓相離的情況，那么轉化后即為求線段不相交的情況，可以將線段的終點按升序排列，如果終點相等的話按起點升序，然后二分查找每一個起點，找到終點大于起點的下標，每次統計下標即可

源程序

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD = 1E9+7; const int N = 100000+5; const int dx[] = {-1,1,0,0}; const int dy[] = {0,0,-1,1}; using namespace std;struct Node {LL l,r;bool operator < (const Node &rhs)const{if(l==rhs.l)return r<rhs.y;return l<rhs.l;} } a[N]; LL start[N],endd[N]; int main() {int n;while(scanf("%d",&n)!=EOF) {LL pos,d;for(int i=1; i<=n; i++) {scanf("%lld%lld",&pos,&d);a[i].l=pos-d;a[i].r=pos+d;}for(int i=0; i<n; i++) {start[i]=a[i+1].l;endd[i]=a[i+1].r;}sort(endd,endd+n);LL ans=0;for(int i=0; i<n; i++)res+=(lower_bound(endd,endd+n,start[i])-(endd));printf("%lld\n",res);}return 0; }

?

總結

以上是生活随笔為你收集整理的相离的圆（51Nod-1278）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。