关键词：
bzoj 1337 最小圆覆盖
补充一个求三角形外心的向量法.用了点积的几何意义,很实用.出处.
使用随机增量法求.首先随机打乱顺序,然后三重循环,选择当前在圆外的点更新圆,分别按照 (1/2/3) 个点确定圆的方式更新即可.
- 由于随机一个点不在前 (i) 个点的最小覆盖圆内的概率是 (frac 3 i) ,可以证明这样的时间复杂度是 (O(n)) 的,这种做法可以推广到常数维度上,时间复杂度仍为 (O(n)) .
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
inline int read()
int x=0;
bool pos=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar())
if(ch=='-')
pos=0;
for(;isdigit(ch);ch=getchar())
x=x*10+ch-'0';
return pos?x:-x;
const double eps=1e-9;
const int MAXN=1e5+10;
int dcmp(double x)
return fabs(x)<=eps?0:(x>0?1:-1);
struct v2
double x,y;
v2(double x=0,double y=0):x(x),y(y)
v2 operator + (const v2 &rhs) const
return v2(x+rhs.x,y+rhs.y);
v2 operator / (const double &rhs) const
return v2(x/rhs,y/rhs);
v2 operator - (const v2 &rhs) const
return v2(x-rhs.x,y-rhs.y);
double operator * (const v2 &rhs) const
return x*rhs.y-y*rhs.x;
double modulus()
return sqrt(x*x+y*y);
;
double dist(v2 a,v2 b)
return (a-b).modulus();
v2 CirCentre(v2 a,v2 b,v2 c)
v2 centre;
double a1=b.x-a.x;
double b1=b.y-a.y;
double c1=(a1*a1+b1*b1)/2.0;
double a2=c.x-a.x;
double b2=c.y-a.y;
double c2=(a2*a2+b2*b2)/2.0;
double d=a1*b2-a2*b1;
centre.x=a.x+(c1*b2-c2*b1)/d;
centre.y=a.y+(a1*c2-a2*c1)/d;
return centre;
bool incircle(v2 p,v2 centre,double r)
return dcmp(dist(p,centre)-r)<=0;
void MinCircleCover(v2 *p,int n,v2 ¢re,double &r)
srand(time(NULL));
random_shuffle(p+1,p+1+n);
centre=p[1];
r=0;
for(int i=2;i<=n;++i)
if(!incircle(p[i],centre,r))
centre=p[i];
r=0;
for(int j=1;j<i;++j)
if(!incircle(p[j],centre,r))
centre=(p[i]+p[j])/2.0;
r=(p[i]-p[j]).modulus()/2.0;
for(int k=1;k<j;++k)
if(!incircle(p[k],centre,r))
centre=CirCentre(p[i],p[j],p[k]);
r=dist(centre,p[i]);
int n;
v2 p[MAXN];
int main()
n=read();
for(int i=1;i<=n;++i)
scanf("%lf%lf",&p[i].x,&p[i].y);
v2 centre;
double r;
MinCircleCover(p,n,centre,r);
printf("%.3lf
",r);
return 0;
bzoj1336/1337/2823[balkan2002]alien最小圆覆盖随机增量法
题目描述给出N个点，让你画一个最小的包含所有点的圆。输入先给出点的个数N,2<=N<=100000，再给出坐标Xi,Yi.(-10000.0<=xi,yi<=10000.0)输出输出圆的半径，及圆心的坐标样例输入68.09.04.07.51.02.05.18.79.02.04.51.0样例输出5.005.005.00题... 查看详情
模板最小圆覆盖——bzoj1336(代码片段)
博客链接https://blog.csdn.net/commonc/article/details/52291822#include<bits/stdc++.h>usingnamespacestd;#defineN100005typedefdoubledb;constdbeps=1e-10;constdbpi=acos(-1);intsign(dbk)if(k>eps)return1;elseif(k<-eps)return-1;return0;intcmp(dbk1,dbk2)returnsign(k1-k2);intinmid(dbk1,dbk2,d... 查看详情
bzoj1336[balkan2002]alien最小圆覆盖随机增量法
【BZOJ1336】[Balkan2002]Alien最小圆覆盖Description给出N个点，让你画一个最小的包含所有点的圆。Input先给出点的个数N,2<=N<=100000，再给出坐标Xi,Yi.(-10000.0<=xi,yi<=10000.0)Output输出圆的半径，及圆心的坐标SampleInput68.09.04.07.51.02.05.... 查看详情
luogup1742最小圆覆盖(代码片段)
最小圆覆盖主要是我太菜了不会证明qwq，上面的博客讲的非常好。主要是存代码：#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>usingnamespacestd;constintN=100009;constdoublee 查看详情
c案例：最小覆盖圆问题(代码片段)
文章目录一、提出任务-最小覆盖圆（一）描述（二）输入（三）输出（四）样例输入输出二、完成任务（一）编程思路（二）编写代码，实现功能（三）运行程序，查... 查看详情
c案例：最小覆盖圆问题(代码片段)
文章目录一、提出任务-最小覆盖圆（一）描述（二）输入（三）输出（四）样例输入输出二、完成任务（一）编程思路（二）编写代码，实现功能（三）运行程序，查... 查看详情
[matlab]10.最小覆盖圆(代码片段)
clearall;closeall;clc;n=100;p=rand(n,2);p1=p(1,:);%取第一行的值P1点p2=p(2,:);%取第二行的值P2点r=sqrt((p1(1)-p2(1))^2+(p1(2)-p2(2))^2)/2;%求两点半径cenp=(p1+p2)/2;%求两点中点fori=3:nnewp=p(i,:);%从第三行开始储存新的点d=sqrt((cenp(1)-new 查看详情
c案例：最小覆盖圆问题(代码片段)
文章目录一、提出任务-最小覆盖圆（一）描述（二）输入（三）输出（四）样例输入输出二、完成任务（一）编程思路（二）编写代码，实现功能（三）运行程序，查... 查看详情
bzoj2280[poi2011]plot二分+倍增+二分+最小圆覆盖
...求一个点q_i，使得q_i到这段内点的距离的最大值的最大值最小输入第一行，nm下面n行，每行两个整数，表示p_i的xy坐标1<=m<=n<=100000坐标范围[-1000000,1000000] 0<p,q,r<=150，输入中至少包含一个’N’ 查看详情
bzoj2044三维导弹拦截——最小路径覆盖(代码片段)
...以先按第一维排序一下即可；然后拆入点和出点，求一个最小路径覆盖即可。代码如下：#include<iostream>#include<cstdio>#include<cstring>#include< 查看详情
bzoj1185[hnoi2007]最小矩形覆盖旋转卡壳求凸包(代码片段)
[HNOI2007]最小矩形覆盖TimeLimit: 10Sec MemoryLimit: 162MBSec SpecialJudgeSubmit: 2081 Solved: 920[Submit][Status][Discuss]Description给定一些点的坐标，要求求能够覆盖所有点的 查看详情
bzoj1185[hnoi2007]最小矩形覆盖：凸包+旋转卡壳(代码片段)
...意： 给出二维平面上的n个点，问你将所有点覆盖的最小矩形面积。 题解： 先找出凸包，然后旋转卡壳。 在旋转卡壳中有一个结论：最小覆盖矩形一定有一条边在凸包上。 所以先枚举矩形在凸包上的那条边(p... 查看详情
bzoj2150.部落战争（最小路径覆盖问题）bzoj千题计划(代码片段)
整理的算法模板合集：ACM模板点我看算法全家桶系列！！！实际上是一个全新的精炼模板整合计划刷题就图一乐题目链接https://hydro.ac/d/bzoj/p/2150是hydro的BZOJ修复工程！题目描述lanzerb的部落在A国的上部，他... 查看详情
bzoj2150.部落战争（最小路径覆盖问题）bzoj千题计划(代码片段)
整理的算法模板合集：ACM模板点我看算法全家桶系列！！！实际上是一个全新的精炼模板整合计划刷题就图一乐题目链接https://hydro.ac/d/bzoj/p/2150是hydro的BZOJ修复工程！题目描述lanzerb的部落在A国的上部，他... 查看详情
覆盖点问题总结(代码片段)
1.最小的包围圆，将所有的点包围起来。（hdu3932）最小覆盖圆算法地址：http://soft.cs.tsinghua.edu.cn/blog/?q=node/1066问题的背景提出：考察固定在工作平台上的一直机械手，要捡起散落在不同位置的多个零件，并送到别的地方。那么，... 查看详情
bzoj2044三维导弹拦截——dag最小路径覆盖（二分图）(代码片段)
...自己转移到哪些状态就从自己向哪些状态连边，然后就是最小路径覆盖了。用二分图的n-最大匹配。注意：没有位置的限制所以可以先按x排序！#include<ios 查看详情
最小圆覆盖gym-102006i(代码片段)
#include<bits/stdc++.h>#defineLLlonglong#definefifirst#definesesecond#definemkmake_pair#definePLLpair<LL,LL>#definePLIpair<LL,int>#definePIIpair<int,int>#defineSZ(x)((int)x.size())#defineullunsignedlonglongusingnamespacestd;constintN=2e5+7;constintinf=0x3f3f3f3f;constLLINF=0x... 查看详情
java案例：最小覆盖圆问题
文章目录一、提出任务-最小覆盖圆（一）描述（二）输入（三）输出（四）样例输入输出二、完成任务（一）编程思路（二）编写代码，实现功能（三）运行程序，查看结果一、提出任务-最小覆盖圆（一）描述给出平面上N(N≤1... 查看详情