首先考虑覆盖三个点的情况,有两种情况:

①:三个点都在圆上,则该圆是三角形的外接圆

②:两个点在圆上,第三个点在圆内,且在圆上的两个点之间的线段一定是直径

如果是多个圆,就不停地迭代。

有一点重要的是外接圆的求法,盗图说明:

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define N 1010
#define eps 1e-7
using namespace std;
int x,y,n;double r;
struct node{
double x,y;
};node p[N],c;
double dis(node i,node j){
return sqrt((i.x-j.x)*(i.x-j.x)+(i.y-j.y)*(i.y-j.y));
}
node get(node p1,node p2,node p3){
node t;
double c1=(p1.x*p1.x-p2.x*p2.x+p1.y*p1.y-p2.y*p2.y)/2.0;
double c2=(p3.x*p3.x-p2.x*p2.x+p3.y*p3.y-p2.y*p2.y)/2.0;
t.x=(c1*(p3.y-p2.y)-c2*(p1.y-p2.y))/((p1.x-p2.x)*(p3.y-p2.y)-(p3.x-p2.x)*(p1.y-p2.y));
t.y=(c1*(p3.x-p2.x)-c2*(p1.x-p2.x))/((p1.y-p2.y)*(p3.x-p2.x)-(p3.y-p2.y)*(p1.x-p2.x));
return t;
}
void work(){
random_shuffle(p,p+n);
c=p[];r=;
for(int i=;i<n;i++)
if(dis(c,p[i])+eps>r){
c=p[i];r=;
for(int j=;j<i;j++)
if(dis(c,p[j])+eps>r){
c.x=(p[i].x+p[j].x)/;//不知道为啥这里写成c.x=(c.x+p[j].x)/2就WA了
c.y=(p[i].y+p[j].y)/;
r=dis(c,p[j]);
for(int k=;k<j;k++)
if(dis(c,p[k])+eps>r){
c=get(p[i],p[j],p[k]);
r=dis(c,p[k]);
}
}
}
printf("(%.1lf,%.1lf).\n%.1lf\n",c.x,c.y,r);
}
int main(){
while(cin>>x>>y>>n){
for(int i=;i<n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
work();
}
return ;
}

网上还有一种求外接圆的方法,然而并没有看懂:

Point circumcenter(const Point &a,const Point &b,const Point &c)
{
Point ret;
double a1=b.x-a.x,b1=b.y-a.y,c1=(a1*a1+b1*b1)/;
double a2=c.x-a.x,b2=c.y-a.y,c2=(a2*a2+b2*b2)/;
double d=a1*b2-a2*b1;
ret.x=a.x+(c1*b2-c2*b1)/d;
ret.y=a.y+(a1*c2-a2*c1)/d;
return ret;
}

最新文章

  1. Oracle 用户管理与权限控制
  2. Android开发中的全屏背景显示方案
  3. NOIP2000进制转换
  4. Fedora 24最新工作站版本之四大重要改进
  5. 图文详解YUV420, yuv格式2
  6. HTML标签之间不是可以随便嵌套的
  7. 多台CentOS服务器时间同步(NTP时间同步)(转)
  8. jquery之wrap(),wrap(),unwrap()方法详解
  9. Windows 7的100M隐藏分区
  10. 给 chorme Developer Tool F12 开发者工具.加入更酷的代码着色
  11. 图片实时预览JSP加js
  12. ajax的理解和运用
  13. 1.centOS安装Mysql
  14. Suneast &amp; Daxia (规律)
  15. Nexus3将本地jar包添加到仓库
  16. ES6 迭代器
  17. linux中pam模块
  18. 用好这6个APP,学英语SO EASY!
  19. Posix共享内存区
  20. nio入门教程

热门文章

  1. 小程序setData,视图层没有跟新
  2. Android学习笔记(十九) OkHttp
  3. JDBC ResultSet分析
  4. COGS 942. [東方S3] 比那名居天子
  5. 原创:Nginx反向代理实战部署
  6. EasyX库进行图片绘制函数
  7. Python3基础教程(十八)—— 测试
  8. uva1336 Fixing the Great Wall
  9. 微信小程序---目录结构
  10. python关于入参中,传入的是指针还是引用