题目描述

给出N个点,让你画一个最小的包含所有点的圆。

输入

先给出点的个数N,2<=N<=100000,再给出坐标Xi,Yi.(-10000.0<=xi,yi<=10000.0)

输出

输出圆的半径,及圆心的坐标

样例输入

6
8.0 9.0
4.0 7.5
1.0 2.0
5.1 8.7
9.0 2.0
4.5 1.0

样例输出

5.00
5.00 5.00


题解

随机增量法求最小圆覆盖裸题

求法:设初始圆为某空圆,先枚举第一个点,如果不在当前圆内,则令当前圆为这一个点的最小圆覆盖并枚举第二个点,如果不在则变为这两个点的最小圆覆盖并枚举第三个点,如果不在则变为这三个点的最小圆覆盖。

看上去是三重循环,但是实际上时间复杂度为期望$O(n)$的,证明参见 http://blog.csdn.net/lthyxy/article/details/6661250

需要先将点随机排序以防止被刻意卡掉。

另外求三个点的公共圆时可以直接套用坐标公式,参见代码。

#include <cmath>
#include <cstdio>
#include <algorithm>
#define N 100010
using namespace std;
const double eps = 1e-15;
double x[N] , y[N];
int id[N];
inline double squ(double x)
{
return x * x;
}
int main()
{
srand(20011011);
int n , i , j , k;
double px = 0 , py = 0 , r = 0 , x1 , x2 , x3 , y1 , y2 , y3;
scanf("%d" , &n);
for(i = 1 ; i <= n ; i ++ ) scanf("%lf%lf" , &x[i] , &y[i]) , id[i] = i;
random_shuffle(id + 1 , id + n + 1);
for(i = 1 ; i <= n ; i ++ )
{
if(squ(px - x[id[i]]) + squ(py - y[id[i]]) > r + eps)
{
px = x[id[i]] , py = y[id[i]] , r = 0;
for(j = 1 ; j < i ; j ++ )
{
if(squ(px - x[id[j]]) + squ(py - y[id[j]]) > r + eps)
{
px = (x[id[i]] + x[id[j]]) / 2 , py = (y[id[i]] + y[id[j]]) / 2 , r = (squ(x[id[i]] - x[id[j]]) + squ(y[id[i]] - y[id[j]])) / 4;
for(k = 1 ; k < j ; k ++ )
{
if(squ(px - x[id[k]]) + squ(py - y[id[k]]) > r + eps)
{
x1 = x[id[i]] , x2 = x[id[j]] , x3 = x[id[k]];
y1 = y[id[i]] , y2 = y[id[j]] , y3 = y[id[k]];
px = (x1 * x1 * (y2 - y3) + x2 * x2 * (y3 - y1) + x3 * x3 * (y1 - y2) - (y1 - y2) * (y2 - y3) * (y3 - y1)) / (x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2;
py = ((x1 - x2) * (x2 - x3) * (x3 - x1) - y1 * y1 * (x2 - x3) - y2 * y2 * (x3 - x1) - y3 * y3 * (x1 - x2)) / (x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2;
r = squ(px - x1) + squ(py - y1);
}
}
}
}
}
}
printf("%.15lf\n%.15lf %.15lf\n" , sqrt(r) , px , py);
return 0;
}

最新文章

  1. [译]Godot系列教程四 - 编写脚本
  2. c/c++常用网址
  3. 网站错误记录:Timeout expired. The timeout period elapsed prior to obtaining a connection from the pool.
  4. android开机自启动广播
  5. [Effective JavaScript 笔记]第15条:当心局部块函数声明笨拙的作用域
  6. 在word中做复选框打对勾钩
  7. iOS里面如何同时使用开启ARC的库 和 没有开启 ARC的库,ARC 与非 ARC同时存在的问题
  8. File类详解
  9. IE, FireFox, Opera 浏览器支持CSS实现Alpha透明的方法 兼容问题
  10. cocos2d-x3.0 lua学习(一个)
  11. Codeforces Round #267 (Div. 2)D(DFS+单词hash+简单DP)
  12. 远程推送-----iOS
  13. JSON Web Token - 在Web应用间安全地传递信息
  14. 阅读源码(III)
  15. 使用swift语言进行IOS应用开发
  16. 关于pom.xml文件中引入net.sf.json-lib出错问题
  17. Spring Boot 2.x (十):构建优雅的RESTful接口
  18. Python学习笔记第九周
  19. Java中递归的优缺点,Java写一个递归遍历目录下面的所有文件包括子文件夹里边的文件。
  20. WampServer下修改和重置MySQL密码

热门文章

  1. Java环境变量搭建(Windows环境)
  2. CUDA并行存储模型
  3. XAMPP安装过程中,出现的问题
  4. Linux yum安装
  5. angular实现全屏显示效果
  6. C/C++程序基础 (四)字符串
  7. node 发送邮件demo (QQ邮箱)
  8. c 语言技巧
  9. composer 自动加载源码解析
  10. VMWare workstation Pro 14 For Linux key