首页 > 代码库 > ZOJ 1450 Minimal Circle 最小圆覆盖

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 <vector>#include <algorithm>#define ll long long#define Max(a,b) (((a) > (b)) ? (a) : (b))#define Min(a,b) (((a) < (b)) ? (a) : (b))#define Abs(x) (((x) > 0) ? (x) : (-(x)))using namespace std;const int INF = 0x3f3f3f3f;const int MAXN = 220;const double eps = 1e-9;struct POINT{    double x;    double y;    POINT() : x(0), y(0) {};    POINT(double _x_, double _y_) : x(_x_), y(_y_) {};};struct CIRCLE{    POINT p;    double r;    CIRCLE() {};    CIRCLE(POINT _p_, double _r_) : p(_p_), r(_r_) {};};double dist(POINT a,POINT b){    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}CIRCLE calc(POINT p1,POINT p2,POINT p3){//三点的外接圆圆心的函数:    CIRCLE temp;    double a,b,c,d,e,f;    a = p2.x - p1.x;    b = p2.y - p1.y;    c = (p2.x * p2.x + p2.y * p2.y - p1.x * p1.x - p1.y * p1.y) / 2;    d = p3.x - p1.x;    e = p3.y - p1.y;    f = (p3.x * p3.x + p3.y * p3.y - p1.x * p1.x - p1.y * p1.y) / 2;    temp.p.y = (c * d - f * a) / (b * d - e * a);    temp.p.x = (c * e - f * b) / (a * e - b * d);    return temp;}CIRCLE minC(POINT *p,int n){    CIRCLE O;    int i,j,k;    O.p = p[0];    O.r = 0;    for(i=  1; i < n ; i++){        if(dist(O.p,p[i]) <= O.r + eps) continue;        O.p = p[i];O.r = 0;        for(j = 0; j < i; j++){            if(dist(O.p,p[j]) <= O.r + eps) continue;            O.p.x = (p[i].x + p[j].x) / 2;            O.p.y = (p[i].y + p[j].y) / 2;            O.r = dist(O.p,p[j]);            for(k = 0; k < j; k++){                if(dist(O.p,p[k]) <= O.r + eps) continue;                O = calc(p[i],p[j],p[k]);                O.r = dist(O.p,p[k]);            }        }    }    return O;}int main(){    int i, j, n;    POINT p[200];    while(EOF != scanf("%d",&n)){        if(n == 0)  break;        for(i = 0; i < n; ++i)            scanf("%lf%lf",&p[i].x,&p[i].y);        CIRCLE c = minC(p, n);        printf("%.2f %.2f %.2f\n",c.p.x,c.p.y,c.r);    }    return 0;}