1031 基站布置

深碍√TFBOYSˉ_ 2022-09-12 02:56 172阅读 0赞

**Description**

海面上有一些船需要与陆地进行通信，需要在海岸线上布置一些基站。现将问题抽象为，在x轴上方，给出n条船的
    坐标p1,p2,…,pn，其中pi=(xi,yi)，0≤yi≤d, 1≤i≤n，在x轴安放的基站可以覆盖半径为d的区域内的所有船只，
    问在x轴至少要安放几个基站才可以将x轴上方的船只都覆盖到。

![9d775dea74e74be413bba900f7c9818b.png][]

**Input**

第一行输入m表示有m组测试. 每组测试首先输入两个整数n(n<=10000)和d，接下来输入n个整数坐标(x,y)，其中0≤y≤d.
    黑色, 其中0和1的个数分别为n个.

**Output**

对每组测试数据输出最小总连线长度.
    
    提示:
    判断两点距离是否小于d可能需要考虑精度损失, 建议使用
    (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) - d*d <= 1e-10
    而非
    (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) <= d*d

**Sample Input**

2
    3 2
    0 1
    2 1
    3 2
    
    4 4
    0 1
    1 1
    2 1
    3 2

**Sample Output**

2
    1
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <math.h>
    struct pos_t {
        double x, y;
        double rsect;
    } pos[10010];
    int cover[10010];
    int n;
    double d;
    
    const double minINF = 0.00000000001;//浮点误差
    
    int cmp(const void *a, const void *b) {
        pos_t *ta, *tb;
        ta = (pos_t *)a;
        tb = (pos_t *)b;
        double temp = ta->rsect-tb->rsect;
        if(-minINF<=temp && temp<=minINF) {//浮点数比较注意预留一定的精度判断
        //if(temp == 0) {
            return 0;
        }
        else if (temp < 0) {
            return -1;
        }
        else {
            return 1;
        }
    }
    
    int solve() {
        scanf("%d%lf", &n, &d);
        for(int i=0; i<n; i++) {
            scanf("%lf%lf", &pos[i].x, &pos[i].y);
            pos[i].rsect = pos[i].x + sqrt(d*d-pos[i].y*pos[i].y);
        }
        memset(cover, 0, sizeof(cover));
        qsort(pos, n, sizeof(pos_t), cmp);
        int count = 0;
        for(int i=0; i<n; i++) {
            if(cover[i] == 1) {
                continue;
            }
            count = count + 1;
            for(int j=i; j<n; j++) {
                if(pos[j].rsect-pos[i].rsect > 2*d) {
                    break;
                }
                if(cover[j]==1) {
                    continue;
                }
                //下面也需要注意浮点误差
                double temp = (pos[j].x-pos[i].rsect)*(pos[j].x-pos[i].rsect) + pos[j].y*pos[j].y - d*d;
                if(temp<=minINF) {
                    cover[j] = 1;
                }
            }
        }
        printf("%d\n", count);
    }
    
    int main() {
        int m;
        scanf("%d", &m);
        for(int i=0; i<m; i++) {
            solve();
        }
        return 0;
    }

[9d775dea74e74be413bba900f7c9818b.png]: /images/20220828/ca024271dc3e42b69c9287768800dd2c.png