BZOJ 1336: [Balkan2002]Alien最小圆覆盖

正文索引 [隐藏]

Description
Input
Output
Sample Input
Sample Output
题解

Description

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

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

题解

随机增量算法！大家可以百度一下！【喂、这哪里体现随即化了啊？
就是我们考虑一个问题，我们有一个圆覆盖C,要往里面加入一个点p。
如果点p在C上或C内，在加入p的情况下C成立。
如果不是这样，那么加入p后的C’一定含有p这个点，且C’上至少有两个点。那么我们穷举p之前的点，计算两个点是圆心和半径。如果这个C’上有3个以上的点，那么我们只要知道3个点就可以确定C’了，那么我们在两个点计算的结果的基础上，穷举，计算是否有更新C’的必要。
网上说经过奇怪的推导证明之后，可以保证是O(n)的、、
这道题目有一个坑点就是不要看样例是两位小数OuQ..我保留2位小数全都Wa掉了！我猜它有SPJ，保留10位就好了。
三倍经验 => BZOJ 1337 2823

#include<cstdio>
#include<cmath>
#include<iostream>
using namespace std;
const int Maxn=100010;
const double EPS=1e-8;
struct P{
    double x,y;
    P(){}
    P(double x0,double y0){
        x=x0;
        y=y0;
    }
};
inline double sqr(double x){return x*x;}
inline double getDist(P a,P b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}
inline double zabs(double x){return (x>=0?x:-x);}
inline P getO(P a,P b,P c){
    double x1=2*(a.x-b.x),x2=2*(a.x-c.x);
    double y1=2*(a.y-b.y),y2=2*(a.y-c.y);
    double z1=sqr(a.x)-sqr(b.x)+sqr(a.y)-sqr(b.y),
            z2=sqr(a.x)-sqr(c.x)+sqr(a.y)-sqr(c.y);
    P ret;
    if (zabs(x1)<=EPS){
        ret.y=z1/y1;
        ret.x=(z2-y2*ret.y)/x2;
        return ret;
    }
    if (zabs(y1)<=EPS){
        ret.x=z1/x1;
        ret.y=(z2-x2*ret.x)/y2;
        return ret;
    }
    ret.y=(z1*x2-z2*x1)/(y1*x2-y2*x1);
    ret.x=(z1*y2-z2*y1)/(x1*y2-x2*y1);
    return ret;
}
int n;
P p[Maxn];
P O;
double R;
P A,B,C;
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%lf%lf",&p[i].x,&p[i].y);
    O=p[1];R=0;
    for (int i=2;i<=n;i++){
        if (zabs(getDist(O,p[i])-R)<=EPS || getDist(O,p[i])<=R) continue;
        O=A=p[i];R=0;
        for (int j=1;j<i;j++){
            if (zabs(getDist(O,p[j])-R)<=EPS || getDist(O,p[j])<=R) continue;
            B=p[j];
            O=P((A.x+B.x)/2,(A.y+B.y)/2);
            R=getDist(A,B)/2;
            for (int k=1;k<j;k++){
                if (zabs(getDist(O,p[k])-R)<=EPS || getDist(O,p[k])<=R) continue;
                C=p[k];
                O=getO(A,B,C);
                R=getDist(O,A);
            }
        }
    }
    printf("%.10lf\n%.10lf %.10lf\n",R,O.x,O.y);
    return 0;
}

#include<cstdio>

#include<cmath>

#include<iostream>

using namespace std;

const int Maxn=100010;

const double EPS=1e-8;

struct P{

double x,y;

P(){}

P(double x0,double y0){

x=x0;

y=y0;

}

};

inline double sqr(double x){return x*x;}

inline double getDist(P a,P b){return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}

inline double zabs(double x){return (x>=0?x:-x);}

inline P getO(P a,P b,P c){

double x1=2*(a.x-b.x),x2=2*(a.x-c.x);

double y1=2*(a.y-b.y),y2=2*(a.y-c.y);

double z1=sqr(a.x)-sqr(b.x)+sqr(a.y)-sqr(b.y),

z2=sqr(a.x)-sqr(c.x)+sqr(a.y)-sqr(c.y);

P ret;

if (zabs(x1)<=EPS){

ret.y=z1/y1;

ret.x=(z2-y2*ret.y)/x2;

return ret;

}

if (zabs(y1)<=EPS){

ret.x=z1/x1;

ret.y=(z2-x2*ret.x)/y2;

return ret;

}

ret.y=(z1*x2-z2*x1)/(y1*x2-y2*x1);

ret.x=(z1*y2-z2*y1)/(x1*y2-x2*y1);

return ret;

}

int n;

P p[Maxn];

P O;

double R;

P A,B,C;

int main(){

scanf("%d",&n);

for (int i=1;i<=n;i++)

scanf("%lf%lf",&p[i].x,&p[i].y);

O=p[1];R=0;

for (int i=2;i<=n;i++){

if (zabs(getDist(O,p[i])-R)<=EPS || getDist(O,p[i])<=R) continue;

O=A=p[i];R=0;

for (int j=1;j<i;j++){

if (zabs(getDist(O,p[j])-R)<=EPS || getDist(O,p[j])<=R) continue;

B=p[j];

O=P((A.x+B.x)/2,(A.y+B.y)/2);

R=getDist(A,B)/2;

for (int k=1;k<j;k++){

if (zabs(getDist(O,p[k])-R)<=EPS || getDist(O,p[k])<=R) continue;

C=p[k];

O=getO(A,B,C);

R=getDist(O,A);

}

printf("%.10lf\n%.10lf %.10lf\n",R,O.x,O.y);

return 0;

}

一	二	三	四	五	六	日
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

WNJXYKの博客

喂你脚下有坑