【bzoj2823】 AHOI2012—信号塔

时间：2023-03-09 02:46:37
【bzoj2823】 AHOI2012—信号塔

http://www.lydsy.com/JudgeOnline/problem.php?id=2823 (题目链接)

题意

　　求最小圆覆盖

Solution

　　关于最小圆覆盖的做法，论文里面都有。其实真正麻烦的是求三角形的外心。

代码

// bzoj2823

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#define eps 1e-10

#define inf 2147483640

#define LL long long

#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);

using namespace std;

inline LL getint() {

    LL x=0,f=1;char ch=getchar();

    while (ch>'9' || ch<'0') {if (ch=='-') f=-1;ch=getchar();}

    while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

const int maxn=1000010;

struct point {double x,y;}p[maxn];

int n;

double dis(point a,point b) {

    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

point center(point a,point b,point c) {

    double a1=b.x-a.x,b1=b.y-a.y,c1=(a1*a1+b1*b1)/2;

    double a2=c.x-a.x,b2=c.y-a.y,c2=(a2*a2+b2*b2)/2;

    double d=a1*b2-a2*b1;

    return (point){a.x+(c1*b2-c2*b1)/d,a.y+(a1*c2-a2*c1)/d};

}

int main() {

    scanf("%d",&n);

    for (int i=1;i<=n;i++) {scanf("%lf%lf",&p[i].x,&p[i].y);swap(p[i],p[rand()%i+1]);}

    point c=p[1];double r=0;

    for (int i=2;i<=n;i++) {

        if (dis(c,p[i])<=r+eps) continue;

        c=p[i];r=0;

        for (int j=1;j<i;j++) {

            if (dis(c,p[j])<=r+eps) continue;

            c.x=(p[i].x+p[j].x)/2;

            c.y=(p[i].y+p[j].y)/2;

            r=dis(c,p[j]);

            for (int k=1;k<j;k++) {

                if (dis(c,p[k])<=r+eps) continue;

                c=center(p[i],p[j],p[k]);

                r=dis(p[k],c);

            }

        }

    }

    printf("%.2f %.2f %.2f",c.x,c.y,r);

    return 0;

}

　　

相关文章