BZOJ 1336&1337最小圆覆盖
2024-09-20 10:16:28
思路:
http://blog.csdn.net/commonc/article/details/52291822
(照着算法步骤写……)
已知三点共圆 求圆心的时候 就设一下圆心坐标(x,y) 解个方程就好了
//By SiriusRen
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
int n;double R,tempx,tempy,tempz,tmpx,tmpy,tmpz;
struct Point{double x,y;}point[100050],Ans;
double Sqr(double x){return x*x;}
double dis(Point a,Point b){return sqrt(Sqr(a.x-b.x)+Sqr(a.y-b.y));}
bool in_circle(Point x){return dis(Ans,x)<=R;}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lf%lf",&point[i].x,&point[i].y);
random_shuffle(point+1,point+n);
for(int i=1;i<=n;i++)if(!in_circle(point[i])){
Ans.x=point[i].x,Ans.y=point[i].y,R=0;
for(int j=1;j<i;j++)if(!in_circle(point[j])){
Ans.x=(point[i].x+point[j].x)/2;
Ans.y=(point[i].y+point[j].y)/2;
R=dis(Ans,point[j]);
for(int k=1;k<j;k++)if(!in_circle(point[k])){
tempz=point[j].x-point[i].x;
tempx=2*(point[i].y-point[j].y)/tempz;
tempy=(Sqr(point[j].x)+Sqr(point[j].y)-Sqr(point[i].x)-Sqr(point[i].y))/tempz;
tmpz=point[k].x-point[j].x;
tmpx=2*(point[j].y-point[k].y)/tmpz;
tmpy=(Sqr(point[k].x)+Sqr(point[k].y)-Sqr(point[j].x)-Sqr(point[j].y))/tmpz;
Ans.y=(tmpy-tempy)/(tempx-tmpx);
Ans.x=(tempx*Ans.y+tempy)/2;
R=dis(Ans,point[j]);
}
}
}
printf("%f\n%f %f\n",R,Ans.x,Ans.y);
}
最新文章
- PHPstorm同步文件时与ftp断开连接
- 将整数转换成二进制的java小程序
- 手把手教你做一个原生js拖动滑块【兼容PC和移动端】
- Windows Phone App Studio 无码开发手机应用
- 手势模型和Angular Material的实现
- JAVA JNI
- window.onload()与$(document).ready()区别
- Code 49 码
- 猎八哥浅谈MYSQL触发器
- CentOS 通过yum来升级php到php5.6
- 小白——java基础之数据类型
- 京东2019春招Java工程师编程题题解
- android 开源图表库MPChart最简单使用方法示例教程Demo--折线图 柱状图
- PHP将图片转base64编码以及base64图片转换为图片并保存代码
- 迁移 Emacs 的自定义设置
- Python基础(九) type元类
- SD
- 如何将本地代码通过git上传到码云
- 本地时间转化成 GMT 时间
- #define后面只带有一个标识符
热门文章
- hdu 4544 湫湫系列故事——消灭兔子 优先队列+贪心
- oracle 下操作blob字段是否会产生大量redo
- bzoj3444: 最后的晚餐(并查集+组合数学)
- 创建一个web user control
- Linux常用命令之rpm安装命令
- [JZOJ NOIP2018模拟10.20 A组]
- [Avito Code Challenge 2018 G] Magic multisets(线段树)
- JqGrid 查询时未设置初始页码导致的问题
- Mojo C++ System API
- PHP读xml、写xml(DOM方法)