M_sea

洛谷2533 [AHOI2012]信号塔
LuoguBZOJ双倍经验分析最小圆覆盖的板子题。首先将输入的点随机打乱,然后三重循环枚举三个点 $i$ 、 $j...
扫描右侧二维码阅读全文
13
2019/03

洛谷2533 [AHOI2012]信号塔

Luogu

BZOJ

双倍经验

分析

最小圆覆盖的板子题。

首先将输入的点随机打乱,然后三重循环枚举三个点 $i$ 、 $j$ 、 $k$ 。

  • 如果 $i$ 不在当前圆内,将圆心设为 $i$ 。
  • 如果 $j$ 也不在圆内,将圆心设为 $i$ 和 $j$ 的中点。
  • 如果 $k$ 也不在圆内,将圆心设为 $△ijk$ 的外心。

可以证明期望复杂度为 $O(n)$ 。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000000+10;
const double eps=1e-10;

int n;
struct Point { double x,y; } p[N];
Point O; double r;

inline double dis(Point a,Point b) {
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline int in_circle(Point a) { return dis(a,O)-r<eps; }

inline Point get_O(Point p,Point q,Point r) {
    double a=q.x-p.x,b=q.y-p.y,c=r.x-q.x,d=r.y-q.y;
    double e=q.x*q.x+q.y*q.y-p.x*p.x-p.y*p.y;
    double f=r.x*r.x+r.y*r.y-q.x*q.x-q.y*q.y;
    return (Point){(f*b-e*d)/(c*b-a*d)/2,(a*f-e*c)/(a*d-b*c)/2};
}

int main() {
    srand(19260817);
    n=read();
    for (re int i=1;i<=n;++i) scanf("%lf%lf",&p[i].x,&p[i].y);
    for (re int i=1;i<=n;++i) swap(p[i],p[rand()%n+1]);
    O=p[1],r=0;
    for (re int i=1;i<=n;++i) {
        if (in_circle(p[i])) continue;
        O=p[i];
        for (re int j=1;j<i;++j) {
            if (in_circle(p[j])) continue;
            O=(Point){(p[i].x+p[j].x)/2,(p[i].y+p[j].y)/2};
            r=dis(p[i],p[j])/2;
            for (re int k=1;k<j;++k) {
                if (in_circle(p[k])) continue;
                O=get_O(p[i],p[j],p[k]),r=dis(O,p[i]);
            }
        }
    }
    printf("%.2lf %.2lf %.2lf\n",O.x,O.y,r);
    return 0;
}
最后修改:2019 年 03 月 13 日 02 : 53 PM

2 条评论

  1. smy

    证明呢qwq

    1. M_sea
      @smy

      不会qwq

发表评论