首页 > 代码库 > HDU 3007

HDU 3007

基本小圆覆盖模板题

#include <iostream>#include <algorithm>#include <cmath>using namespace std;int X,Y; int n;const double eps=0.00000001;struct point{    double x,y;}p[550]; struct Circle{    point cent;    double r;}cir; double dist(point x, point y){    double a=x.x-y.x;    double b=x.y-y.y;    return sqrt(a*a+b*b);} double triangleArea(point t1, point t2, point t3){    point p1,p2;    p1.x=t2.x-t1.x; p1.y=t2.y-t1.y;    p2.x=t3.x-t1.x; p2.y=t3.y-t1.y;    return fabs(p1.x*p2.y-p1.y*p2.x)/2;} Circle triangleCircle(point t1, point t2, point t3){    Circle tmp;    double a=dist(t1,t2);    double b=dist(t2,t3);    double c=dist(t3,t1);    tmp.r=a*b*c/triangleArea(t1,t2,t3)/4;    double xa,ya,xb,yb,xc,yc;    double c1,c2;    xa=t1.x; ya= t1.y;    xb=t2.x; yb= t2.y;    xc=t3.x; yc= t3.y;    c1=(xa*xa+ya*ya-xb*xb-yb*yb)/2;    c2=(xa*xa+ya*ya-xc*xc-yc*yc)/2;    tmp.cent.x=(c1*(ya-yc)-c2*(ya-yb))/((xa-xb)*(ya-yc)-(xa-xc)*(ya-yb));    tmp.cent.y=(c1*(xa-xc)-c2*(xa-xb))/((ya-yb)*(xa-xc)-(ya-yc)*(xa-xb));    return tmp;}void slove(){    random_shuffle(p,p+n);    cir.cent=p[0];    cir.r=0;    for(int i=1;i<n;i++){        if(dist(cir.cent,p[i])>cir.r){            cir.cent=p[i]; cir.r=0;            for(int j=0;j<i;j++){                if(dist(cir.cent,p[j])>cir.r){                    cir.cent.x=(p[i].x+p[j].x)/2;                    cir.cent.y=(p[i].y+p[j].y)/2;                    cir.r=dist(p[i],p[j])/2;                    for(int k=0;k<j;k++){                        if(dist(cir.cent,p[k])>cir.r){                            cir=triangleCircle(p[i],p[j],p[k]);                        }                    }                }            }        }    }}int main (){    while(scanf("%d",&n),n){        for(int i=0;i<n;i++){            scanf("%lf%lf",&p[i].x,&p[i].y);        }        slove();        printf("%0.2lf %0.2lf ",cir.cent.x,cir.cent.y);        printf("%0.2lf\n",cir.r);    }    return 0;}