bzoj 2823(计算几何+最小覆盖圆)

短命女 2022-06-08 10:52 173阅读 0赞

问题描述:

在野外训练中，为了确保每位参加集训的成员安全，实时的掌握和收集周边环境和队员信息非常重要，集训队采用

的方式是在训练所在地散布N个小型传感器来收集并传递信息，这些传感器只与设在集训地中的信号塔进行通信，

信号塔接收信号的覆盖范围是圆形，可以接收到所有分布在该集训区域内所有N个小型传感器（包括在该圆形的边

上）发出的信号。信号塔的功率与信号塔接收范围半径的大小成正比，因为是野外训练，只能使用事先储备好的蓄

电设备，因此在可以收集所有传感器信息的基础上，还应使得信号塔的功率最小。小龙帮助教官确定了一种信号塔

设置的方案，既可以收集到所有N个传感器的信号，又可以保证这个信号塔的功率是最小的。同学们，你们知道，

这个信号塔的信号收集半径有多大，它应该设置在何处吗？

Input

共N+1行，第一行为正整数N（1≤N≤1000000），表示队员个数。接下来N行，每行两个实数用空格分开，分别是第

i个队员的坐标X

Output

一行，共三个实数（中间用空格隔开），分别是信号塔的坐标，和信号塔 覆盖的半径。 （注：队员是否在边界上

的判断应符合他到圆心的距离与信号塔接收半径之差的绝对值小于10^-6

Sample Input

5 
    1.200 1.200 
    2.400 2.400 
    3.800 4.500 
    2.500 3.100 
    3.900 1.300

Sample Output

2.50 2.85 2.10

题目题意:最小覆盖圆算法.

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    using namespace std;
    
    const int maxn=1e6+10;
    struct  Point
    {
        double x,y;
    };
    struct Point a[maxn],d;
    double r;
    
    double  get_dis(Point p1,Point  p2)   //两点间距离
    {
        return (sqrt((p1.x-p2.x)*(p1.x -p2.x)+(p1.y-p2.y)*(p1.y-p2.y)));
    }
    double get_muti(Point p1, Point p2,Point p0)
    {
        return   ((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));
    }
    void get_o(Point p,Point q,int n)
    {
        d.x=(p.x+q.x)/2.0;
        d.y=(p.y+q.y)/2.0;
        r=get_dis(p,q)/2;
        int k;
        double c1,c2,t1,t2,t3;
        for(k=1;k<=n;k++) {
            if(get_dis(d,a[k])<=r)continue;
            if(get_muti(p,q,a[k])!=0.0) {
                c1=(p.x*p.x+p.y*p.y-q.x*q.x-q.y*q.y)/2.0;
                c2=(p.x*p.x+p.y*p.y-a[k].x*a[k].x-a[k].y*a[k].y)/2.0;
                d.x=(c1*(p.y-a[k].y)-c2*(p.y-q.y))/((p.x-q.x)*(p.y-a[k].y)-(p.x-a[k].x)*(p.y-q.y));
                d.y=(c1*(p.x-a[k].x)-c2*(p.x-q.x))/((p.y-q.y)*(p.x-a[k].x)-(p.y-a[k].y)*(p.x-q.x));
                r=get_dis(d,a[k]);
            }
            else {
                t1=get_dis(p,q);
                t2=get_dis(q,a[k]);
                t3=get_dis(p,a[k]);
                if(t1>=t2&&t1>=t3) {
                    d.x=(p.x+q.x)/2.0;
                    d.y=(p.y+q.y)/2.0;r=get_dis(p,q)/2.0;
                }
                else if(t2>=t1&&t2>=t3) {
                    d.x=(a[k].x+q.x)/2.0;
                     d.y=(a[k].y+q.y)/2.0;
                     r=get_dis(a[k],q)/2.0;
                }
                else {
                    d.x=(a[k].x+p.x)/2.0;
                    d.y=(a[k].y+p.y)/2.0;
                    r=get_dis(a[k],p)/2.0;
                }
            }
        }
    }
    
    void solve(Point pi,int n)
    {
        d.x=(pi.x+a[1].x)/2.0;
        d.y=(pi.y+a[1].y)/2.0;
        r=get_dis(pi,a[1])/2.0;
        int j;
        for(j=2;j<=n;j++){
        if(get_dis(d,a[j])<=r)continue;
            else
                get_o(pi,a[j],j-1);
        }
    }
    int main()
    {
        int n;
        while (scanf("%d",&n)!=EOF) {
            for (int i=1;i<=n;i++)
                scanf("%lf%lf",&a[i].x,&a[i].y);
            if(n==1)   { printf("%.7f %.7f 0.00000\n",a[1].x,a[1].y);continue;}
            r=get_dis(a[1],a[2])/2.0;
            d.x=(a[1].x+a[2].x)/2.0;
            d.y=(a[1].y+a[2].y)/2.0;
            for(int i=3;i<=n;i++){
                if(get_dis(d,a[i])<=r)continue;
                else
                solve(a[i],i-1);
            }
            printf("%.6f %.6f %.6f\n",d.x,d.y,r);
        }
        return 0;
    }