当前位置：网站首页>51nod 1278 相离的圆

51nod 1278 相离的圆

2022-07-15 11:43:00 【51CTO】

平面上有N个圆，他们的圆心都在X轴上，给出所有圆的圆心和半径，求有多少对圆是相离的。

例如：4个圆分别位于1, 2, 3, 4的位置，半径分别为1, 1, 2, 1，那么{1, 2}, {1, 3} {2, 3} {2, 4} {3, 4}这5对都有交点，只有{1, 4}是相离的。

Input

第1行：一个数N，表示圆的数量(1 <= N <= 50000) 第2 - N + 1行：每行2个数P, R中间用空格分隔，P表示圆心的位置，R表示圆的半径(1 <= P, R <= 10^9)

Output

输出共有多少对相离的圆。

Input示例

4 1 1 2 1 3 2 4 1

Output示例

把所有圆的头和尾记录下来，标记他们是头还是尾（因为全都在一条直线上）

所以就变成了线段的相交问题。

点的数量就变成了圆的数量的两倍，然后在每一次从头到尾时记录里面有多少圆的头部，说明有多少个重合的，然后到尾时用总数减去这些重合的。

排序的时候要注意按点的位置排，如果左边的点位置一样，就按谁是头谁优先来排。

代码如下：

       
       #include<cstdio>
       
       #include<cstring>
       
       #include<iostream>
       
       #include<algorithm>
       
       using 
       
       namespace 
       
       std;
       
       #define N 100010
       
       struct 
       
       rng{
       
       int 
       
       p,
       
       tmp;
       
}
       
       a[
       
       N];
       
       int 
       
       cmp(
       
       rng 
       
       x,
       
       rng 
       
       y){
       
       if(
       
       x.
       
       p
       
       <
       
       y.
       
       p) 
       
       return 
       
       1;
       
       else 
       
       if(
       
       x.
       
       p
       
       ==
       
       y.
       
       p
       
       &&
       
       x.
       
       tmp
       
       ==
       
       0) 
       
       return 
       
       1;
       
       return 
       
       0;
       
}
       
       int 
       
       main(){
       
       int 
       
       i,
       
       j,
       
       n,
       
       m,
       
       x,
       
       y;
       
       scanf(
       
       "%d",
       
       &
       
       n);
       
       int 
       
       num
       
       =
       
       0;
       
       for(
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       n;
       
       i
       
       ++){
       
       scanf(
       
       "%d %d",
       
       &
       
       x,
       
       &
       
       y);
       
       a[
       
       ++
       
       num].
       
       p
       
       =
       
       x
       
       -
       
       y;
       
       a[
       
       num].
       
       tmp
       
       =
       
       0;
       
       a[
       
       ++
       
       num].
       
       p
       
       =
       
       x
       
       +
       
       y;
       
       a[
       
       num].
       
       tmp
       
       =
       
       1;
       
    }
       
       sort(
       
       a
       
       +
       
       1,
       
       a
       
       +
       
       1
       
       +
       
       num,
       
       cmp);
       
       int 
       
       res
       
       =
       
       0;
       
       int 
       
       sum
       
       =
       
       n;
       
       for(
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       num;
       
       i
       
       ++){
       
       if(
       
       a[
       
       i].
       
       tmp
       
       ==
       
       0) 
       
       sum
       
       --;
       
       else 
       
       if(
       
       a[
       
       i].
       
       tmp
       
       ==
       
       1) 
       
       res
       
       +=
       
       sum;
       
    }
       
       printf(
       
       "%d\n",
       
       res);
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15719342/5475077

当前位置：网站首页>51nod 1278 相离的圆

51nod 1278 相离的圆

边栏推荐

猜你喜欢

随机推荐