#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=505;
int n;
double r;
struct dian
double x,y;
dian(double X=0,double Y=0)
x=X,y=Y;
dian operator + (const dian &a) const
return dian(x+a.x,y+a.y);
dian operator - (const dian &a) const
return dian(x-a.x,y-a.y);
dian operator * (const double &a) const
return dian(x*a,y*a);
dian operator / (const double &a) const
return dian(x/a,y/a);
p[N],c;
double dis(dian a,dian b)
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
double cj(dian a,dian b)
return a.x*b.y-a.y*b.x;
dian yx(dian a,dian b,dian c)
dian p=b-a,q=c-a;
double c1=(p.x*p.x+p.y*p.y)/2,c2=(q.x*q.x+q.y*q.y)/2,d=cj(p,q);
return a+dian(c1*q.y-c2*p.y,c2*p.x-c1*q.x)/d;
int main()
while(scanf("%d",&n)&&n)
for(int i=1;i<=n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
random_shuffle(p+1,p+1+n);
c=p[1],r=0;
for(int i=2;i<=n;i++)
if(dis(p[i],c)-r>0)
c=p[i],r=0;
for(int j=1;j<i;j++)
if(dis(p[j],c)-r>0)
c=(p[i]+p[j])/2,r=dis(p[j],c);
for(int k=1;k<j;k++)
if(dis(p[k],c)-r>0)
c=yx(p[i],p[j],p[k]),r=dis(p[k],c);
printf("%.2f %.2f %.2f\n",c.x,c.y,r);
return 0;
关键词：
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.... 查看详情
bzoj1337最小圆覆盖(代码片段)
bzoj1337最小圆覆盖补充一个求三角形外心的向量法.用了点积的几何意义,很实用.出处.使用随机增量法求.首先随机打乱顺序,然后三重循环,选择当前在圆外的点更新圆,分别按照(1/2/3)个点确定圆的方式更新即可.由于随机一个点不在... 查看详情
p1742最小圆覆盖(代码片段)
(color#0066ff题目描述)给出N个点，让你画一个最小的包含所有点的圆。(color#0066ff输入格式)先给出点的个数N,2<=N<=100000，再给出坐标Xi,Yi.(-10000.0<=xi,yi<=10000.0)(color#0066ff输出格式)输出圆的半径，及圆心的坐标，保留10位小数(c... 查看详情
使用增量邻域法以迭代方式为 voronoi 图逐个像素构建圆
...增量邻域方法在图像中创建Voronoi图，该方法由给定的n个随机点（将是一个像素） 查看详情
做题poi2011r1-plot——最小圆覆盖&倍增(代码片段)
...将其划分成不超过(m)段连续的区间，使得所有每个区间的最小圆覆盖的半径的最大值最小。输出这个最小化的最大值和方案（圆心）。(n,mleq10^5)显然要二分答案。然后，一个区间就是越长越好。首先，考虑最小圆覆盖(O(n))的随机... 查看详情
poj2069最小球覆盖几何法和退火法
对这种问题不熟悉的读者可以先去看一看最小圆覆盖的问题ZOJ1450现在我们来看最小球覆盖问题POJ2069 题目很裸，给30个点求能覆盖所有点的最小球的半径。先给出以下几个事实：1.对于一个点，球心就是这个点且半径无穷小。... 查看详情
覆盖点问题总结(代码片段)
1.最小的包围圆，将所有的点包围起来。（hdu3932）最小覆盖圆算法地址：http://soft.cs.tsinghua.edu.cn/blog/?q=node/1066问题的背景提出：考察固定在工作平台上的一直机械手，要捡起散落在不同位置的多个零件，并送到别的地方。那么，... 查看详情
java案例：最小覆盖圆问题
文章目录一、提出任务-最小覆盖圆（一）描述（二）输入（三）输出（四）样例输入输出二、完成任务（一）编程思路（二）编写代码，实现功能（三）运行程序，查看结果一、提出任务-最小覆盖圆（一）描述给出平面上N(N≤1... 查看详情
java案例：最小覆盖圆问题
文章目录一、提出任务-最小覆盖圆（一）描述（二）输入（三）输出（四）样例输入输出二、完成任务（一）编程思路（二）编写代码，实现功能（三）运行程序，查看结果一、提出任务-最小覆盖圆（一）描述给出平面上N(N≤1... 查看详情
java案例：最小覆盖圆问题
文章目录一、提出任务-最小覆盖圆（一）描述（二）输入（三）输出（四）样例输入输出二、完成任务（一）编程思路（二）编写代码，实现功能（三）运行程序，查看结果一、提出任务-最小覆盖圆（一）描述给出平面上N(N≤1... 查看详情
最小圆覆盖
求一个半径最小的圆使其内部至少包含m个点#include<bits/stdc++.h>usingnamespacestd;#defineMn305constdoubleeps=1e-7;constdoublepi=acos(-1.0);structPoint doublex,y; Point() Point(doubletx,doublety) x=tx; y=ty; 查看详情
mapletrees（最小覆盖圆）
MapletreesTimeLimit:1000/1000MS(Java/Others)MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):222AcceptedSubmission(s):79 ProblemDescriptionTherearealotoftreesinHDU.Kikiwanttosurroundallthe 查看详情
[hdu3264]open-airshoppingmalls（二分+两圆相交面积）
...圆点作圆，这个圆的要求是：你画完以后。这个圆要可以覆盖之前给出的每一个圆一半以上的面积，即覆盖1/2以上每一个圆的面积。比如例子数据，选左边还是选右边没差别，红色的圆为答案（选了左边的圆点），它覆盖了左边... 查看详情
bzoj2823:[ahoi2012]信号塔&&1336:[balkan2002]alien最小圆覆盖&&1337:最小圆覆盖(代码片段)
首先我写了个凸包就溜了这是最小圆覆盖问题，今晚学了一下先随机化点，一个个加入假设当前圆心为o，半径为r，加入的点为i若i不在圆里面，令圆心为i，半径为0再重新从1~i-1不停找j不在圆里面，令圆心为ij中点，直径为ij距... 查看详情
hdu-3644：achocolatemanufacturer'sproblem（模拟退火，求多边形内最大圆半径）(代码片段)
...有效。 学习了下模拟退火的算法，这个随机算法只在最小圆覆盖的时候写过。这里再学一下，看起来更正宗一点的。&nb 查看详情
最小圆覆盖
1structPoint{doublex,y;};2structCircle{Pointc;doubler;};3doubledist(Pointa,Pointb){4returnsqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));5}6Circlecalc(Pointp1,Pointp2,Pointp3){7Circletemp;8doublea,b,c, 查看详情
luogup1742最小圆覆盖(代码片段)
最小圆覆盖主要是我太菜了不会证明qwq，上面的博客讲的非常好。主要是存代码：#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<cmath>usingnamespacestd;constintN=100009;constdoublee 查看详情
c案例：最小覆盖圆问题(代码片段)
文章目录一、提出任务-最小覆盖圆（一）描述（二）输入（三）输出（四）样例输入输出二、完成任务（一）编程思路（二）编写代码，实现功能（三）运行程序，查... 查看详情