wy's Blog

1336: [Balkan2002]Alien最小圆覆盖

Description

Input

Output

Sample Input

Sample Output

算法如题，最小圆覆盖。。。

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MaxN=100010;
const double eps=1e-8;
int N;
struct point{
    double x,y;
    point (double a=0,double b=0){
        x=a; y=b;
    }
     
}P[MaxN],O;
double R;
double dist(const point &a,const point &b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int sgn(const double &x) {
    if (fabs(x) < eps) return 0;
    return x > 0 ? 1 : -1; 
}
bool In(const point &a){
    //return sgn(dist(a, O)-R)<=0;
    return dist(a,O)<=R+eps;           //Ps:以上两种方法同义，只是形式不同
}
void QueryO(const point &a,const point &b,const point &c){
    double A=a.x*a.x-b.x*b.x+a.y*a.y-b.y*b.y,B=(b.x-a.x)*2,C=(b.y-a.y)*2;  //A+Bx+Cy=0
    double D=c.x*c.x-b.x*b.x+c.y*c.y-b.y*b.y,E=(b.x-c.x)*2,F=(b.y-c.y)*2;  //D+Ex+Fy=0
    O.x=(D*C-A*F)/(B*F-E*C); 
    O.y=(D*B-A*E)/(C*E-F*B);
}
int main(){
    scanf("%d",&N);
    for (int i=1;i<=N;++i)
        scanf("%lf%lf",&P[i].x,&P[i].y);
    random_shuffle(P+1,P+N+1);
    R=0;
    O=P[1];
    for (int i=1;i<=N;++i)
        if (!In(P[i])){
            O=P[i];
            R=0;
            for (int j=i-1;j>=1;--j)
                if (!In(P[j])){
                    O.x=(P[i].x+P[j].x)/2;
                    O.y=(P[i].y+P[j].y)/2;
                    R=dist(P[j],O);
                    for (int k=j+1;k<i;++k)
                        if (!In(P[k])){
                            QueryO(P[i],P[j],P[k]);
                            R=dist(P[k],O);
                        }
                }       
        }
    printf("%.10lf\n",R);
    printf("%.10lf %.10lf\n",O.x,O.y);
}

要注意的是对于精度误差的处理（eps的使用）。。。

wy把方程通解的式子求错了，然后WA了一整屏TAT......