Enchantress(hdu 3922)
2024-08-30 14:12:13
首先考虑覆盖三个点的情况,有两种情况:
①:三个点都在圆上,则该圆是三角形的外接圆
②:两个点在圆上,第三个点在圆内,且在圆上的两个点之间的线段一定是直径
如果是多个圆,就不停地迭代。
有一点重要的是外接圆的求法,盗图说明:
#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;
}
最新文章
- Oracle 用户管理与权限控制
- Android开发中的全屏背景显示方案
- NOIP2000进制转换
- Fedora 24最新工作站版本之四大重要改进
- 图文详解YUV420, yuv格式2
- HTML标签之间不是可以随便嵌套的
- 多台CentOS服务器时间同步(NTP时间同步)(转)
- jquery之wrap(),wrap(),unwrap()方法详解
- Windows 7的100M隐藏分区
- 给 chorme Developer Tool F12 开发者工具.加入更酷的代码着色
- 图片实时预览JSP加js
- ajax的理解和运用
- 1.centOS安装Mysql
- Suneast &; Daxia (规律)
- Nexus3将本地jar包添加到仓库
- ES6 迭代器
- linux中pam模块
- 用好这6个APP,学英语SO EASY!
- Posix共享内存区
- nio入门教程