BZOJ 1337: 最小圆覆盖

正文索引 [隐藏]

Description
Input
Output
Sample Input
Sample Output
题解

Description

给出平面上N个点,N<=10^5.请求出一个半径最小的圆覆盖住所有的点

Input

第一行给出数字N，现在N行，每行两个实数x,y表示其坐标.

Output

输出最小半径，输出保留三位小数.

Sample Input

4
1 0
0 1
0 -1
-1 0

Sample Output

1.000

题解

三倍经验 => 2823 1336

#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("%.3lf\n",R);
    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("%.3lf\n",R);

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の博客

喂你脚下有坑