Bzoj 1336&1337 Alien最小圆覆盖

1336: [Balkan2002]Alien最小圆覆盖

Time Limit: 1 Sec  Memory Limit: 162 MBSec  Special Judge
Submit: 1473  Solved: 648
[Submit][Status][Discuss]

Description

Input

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

Output

Sample Input

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

Sample Output

5.00
5.00 5.00

随机增量法求最小圆覆盖。

三重循环。

令ci为前i个点的覆盖圆,新加入一个点i+1时,若其在圆内,跳过,若其在圆外,修改圆心使i+1在圆c(i+1)上。

检查之前的点,令ci为前i个点的覆盖圆,且点j在圆周上,若第i+1个点无法被圆覆盖,修改圆心使点i+1和点j都在圆周上。

检查之前的点,令ci为前i个点的覆盖圆,且点j和点k在圆周上,若第i+1个点无法被圆覆盖,修改圆心使点i+1和点j、点k都在圆周上

这算法倒是还能理解,但是求外心的几何算法表示看不懂。这个技能还是等高二再解锁吧。

代码目前只是过了样例,没有测过。

——辣鸡权限题!

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 using namespace std;
 6 const double eps=1e-8;
 7 const int mxn=100000;
 8 int n;
 9 struct point{
10     double x,y;
11     friend point operator +(const point a,const point b){
12         return (point){a.x+b.x,a.y+b.y};
13     }
14     friend point operator -(const point a,const point b){
15         return (point){a.x-b.x,a.y-b.y};
16     }
17     friend point operator /(const point a,double b){
18         return (point){a.x/b,a.y/b};
19     }
20 }p[mxn];
21 inline double dis(point a,point b){
22     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
23 }
24
25 point center(point a,point b,point c){//返回三角形外心
26     double a1,a2,b1,b2,c1,c2;
27     point ans;
28     a1=2*(b.x-a.x);b1=2*(b.y-a.y);c1=(b.x*b.x)-(a.x*a.x)+(b.y*b.y)-(a.y*a.y);
29     //c1=(a1*a1+b1*b1)/2
30     a2=2*(c.x-a.x);b2=2*(c.y-a.y);c2=(c.x*c.x)-(a.x*a.x)+(c.y*c.y)-(a.y*a.y);
31     //c2=(a2*a2+b2*b2)/2
32     if(fabs(a1)<eps){
33         ans.y=c1/b1;
34         ans.x=(c2-ans.y*b2)/a2;
35     }
36     else if(fabs(b1)<eps){
37         ans.x=c1/a1;
38         ans.y=(c2-ans.x*a2)/b2;
39     }
40     else{
41         ans.x=(c2*b1-c1*b2)/(a2*b1-a1*b2);
42         ans.y=(c2*a1-c1*a2)/(b2*a1-b1*a2);
43     }
44     return ans;
45 }
46 int main(){
47     scanf("%d",&n);
48     int i,j,k;
49     for(i=1;i<=n;i++){
50         scanf("%lf%lf",&p[i].x,&p[i].y);
51     }
52     random_shuffle(p+1,p+n+1);
53     point t=p[1];
54     double r=0.0;
55     for(i=2;i<=n;i++)//
56       if(dis(t,p[i])>r+eps){
57           t=(p[i]+p[1])/2;//默认圆心,等待增量
58           r=dis(p[i],t);//半径
59           for(j=2;j<i;j++)//
60             if(dis(t,p[j])>r+eps){//若有点在圆外,更新圆心
61                 t=(p[i]+p[j])/2;
62                 r=dis(t,p[i]);
63                 for(k=1;k<j;k++){//最多三点确定一圆
64                     if(dis(p[k],t)>r+eps){
65                         t=center(p[i],p[j],p[k]);
66                         r=dis(p[i],t);
67                 }
68             }
69         }
70     }
71     printf("%.10lf\n%.10lf %.10lf",r,t.x,t.y);
72     return 0;
73 }
时间: 07-08

Bzoj 1336&1337 Alien最小圆覆盖的相关文章

【BZOJ-1336&amp;1337】Alie最小圆覆盖 最小圆覆盖(随机增量法)

1336: [Balkan2002]Alien最小圆覆盖 Time Limit: 1 Sec  Memory Limit: 162 MBSec  Special JudgeSubmit: 1573  Solved: 697[Submit][Status][Discuss] Description 给出N个点,让你画一个最小的包含所有点的圆. Input 先给出点的个数N,2<=N<=100000,再给出坐标Xi,Yi.(-10000.0<=xi,yi<=10000.0) Outpu

BZOJ1337: 最小圆覆盖

题目:求n个点的最小圆覆盖. 题解:最小圆覆盖,上模板.复杂度证明可以戳:这里 代码: 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #inclu

最小圆覆盖模板

//最小圆覆盖 //输入: 从下标0开始的点集_ps和大小_n //输出: 覆盖所有点的最小圆 //复杂度: O(n) //注意: 会对_ps进行随机处理操作,将会改变点集的内部顺序 Circle MinCoverCir(Point _ps[],int _n) { //随机处理,但是会改变传入的点集. random_shuffle(_ps, _ps+_n);//复杂度O(_n) Circle rec; rec.r = 0; rec.c = _ps[0]; for(int i=1;i<_n;i++

ZOJ 1450 Minimal Circle 最小圆覆盖

套了个模板直接上,貌似没有随机化序列 QAQ //#pragma comment(linker, "/STACK:16777216") //for c++ Compiler #include <stdio.h> #include <iostream> #include <cstring> #include <cmath> #include <stack> #include <queue> #include <

最小圆覆盖 hdu 3007

今天学习了一下最小圆覆盖, 看了一下午都没看懂, 晚上慢慢的摸索这代码,接合着别人的讲解, 画着图跟着代码一步一步的走着,竟然有些理解了. 最小圆覆盖: 给定n个点, 求出半径最小的圆可以把这些点全部包围, 可以在圆的边界上 下面是我的个人理解. 如果不对, 还请路过大牛指出 先找一个点, 让圆心等于这个点的坐标, 半径等于0, 显然这个对的, 接着找下一个点, 如果只有两个点的话, 那么最小的圆一定是以他们为直径做圆, 接着找第三个点, 如果第三个点在园内或者在边界上, 那么不用更新当前的最小

BZOJ 1337 最小圆覆盖 随机增量法

题意:链接 方法:随机增量法 解析: 首先把所有点打乱. 然后枚举第一个点,如果不在当前的圆内则把它设为圆心. 再枚举第二个点,如果不在当前的圆内则把圆设为其与第一个点的距离为直径的圆. 再枚举第三个点,如果不在当前的圆内则把圆设为这三个点构成三角形的外接圆. 然后最后就是答案了. 别问我这为什么是对的- -! 复杂度期望O(n),我是信了. 代码: #include <cmath> #include <cstdio> #include <iomanip> #inclu

BZOJ 1185 HNOI 2007 最小矩形覆盖 旋转卡壳

题目大意:给出平面上的一些点,问面积最小的矩形满足覆盖所有的点. 思路:覆盖问题和不是凸包上的点没关系,先做凸包.根据贪心的思想,这个覆盖了所有点的矩形肯定至少有一条边与凸包上的边重合,那么我们枚举凸包上的每一条边,对于这个已经确定了一条边的矩形,不难确定其他三个边.注意到已知当前直线的向量,就可以求出两侧和对面的向量,而这三个向量随着枚举的边的移动是单调的,所以就可以用旋转卡壳来卡住剩下的三条边. 但是旋转卡壳时的初值会出问题,如果按照逆时针的顺序求出剩下的三条边的时候,要想通过向量直接卡第三

计算几何模板 (bzoj 1336,poj 2451 ,poj3968)

poj 3968 (bzoj 2642) 二分+半平面交,每次不用排序,这是几个算几版综合. #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<deque> using namespace std; #define MAXN 100000 na

求一个覆盖所有点的最小圆 最小圆覆盖

题目大意:平面上有n个点,求绘制一个半径最小的圆,覆盖所有的点  精度0.1  点的坐标最大为 100000 方法1:http://wenku.baidu.com/view/584b6d3e5727a5e9856a610d.html   O(n) 方法2:三分套三分暴力求解如下.O(1600 n)时间开销  1600~(log  2/3  0.1/100000) ^2 1 float disy(float y,float x) 2 { 3 int n=pvec.size(); 4 float R

最小圆覆盖(Smallest Enclosing Discs)

随机增量算法(a randomized incremental algorithm) #define sqr(x) ((x)*(x)) #define EPS 1e-4 struct P{ double x, y; P(double x, double y):x(x),y(y){} P(P &a, P &b):x(b.x-a.x),y(b.y-a.y){} P(){} P mid(P &a){ return P((a.x+x)/2, (a.y+y)/2); } double cro