AHOI2012 信号塔 | 最小圆覆盖模板

题目链接:戳我

最小圆覆盖。

1、枚举第一个点,考虑当前圆是否包含了这个点,如果没有,则把圆变成以这个点为圆心,半径为0的圆。

2、枚举第二个点,考虑圆是否包含了这个点,如果没有,则把圆变成以这两个点的中点为圆心,半径为两点距离一半的圆。

3、枚举第三个点,节点是否在圆内,如果不在,直接把圆变成这三个点的外接圆。具体怎么做,就是解方程(文化课应该在九年级数学讲到过)

记得要打乱点的顺序!期望时间复杂度为\(O(n)\)(具体为什么我也不知道,但是或许可以感性地理解一下。。。)

另外,如果不想掉精度太严重,还是建议除法都移项,换成乘法。

update:2019.4.4

代码如下:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<ctime>
#define eps 1e-15
#define MAXN 500010
using namespace std;
int n;
double r;
struct Node{double x,y;}node[MAXN],o;
inline double dist(Node a,Node b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
inline void solve(Node A,Node B,Node C)
{
double a=(B.x-C.x)*2;
double b=(B.y-C.y)*2;
double c=(A.x-B.x)*2;
double d=(A.y-B.y)*2;
double e=(B.x*B.x-C.x*C.x)+(B.y*B.y-C.y*C.y);
double f=(A.x*A.x-B.x*B.x)+(A.y*A.y-B.y*B.y);
o.x=(d*e-b*f)/(a*d-b*c);
o.y=(c*e-a*f)/(b*c-a*d);
r=dist(A,o);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("ce.in","r",stdin);
#endif
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf%lf",&node[i].x,&node[i].y);
random_shuffle(&node[1],&node[n+1]);
o.x=node[1].x,o.y=node[1].y;r=0;
for(int i=2;i<=n;i++)
{
if(dist(node[i],o)>r+eps)
{
o=node[i];r=0;
for(int j=1;j<i;j++)
{
if(dist(node[j],o)>r+eps)
{
o.x=(node[j].x+node[i].x)/2;
o.y=(node[j].y+node[i].y)/2;
r=dist(o,node[i]);
for(int k=1;k<j;k++)
{
if(dist(node[k],o)>eps+r)
solve(node[k],node[i],node[j]);
}
}
}
}
}
printf("%.2lf %.2lf %.2lf\n",o.x,o.y,r);
return 0;
}
上一篇:LightOj 1265 - Island of Survival(概率)


下一篇:半年的iOS代码生活