首页 > 代码库 > HDU 3932

HDU 3932

2024-07-15 08:49:53   222人阅读

最小圆覆盖问题。

根据黑书上的算法写的。定理：PI不在当前的圆内，则必在扩张后的圆上，即扩张后的圆必定经过PI。因为求最小圆使用的是点增量法，把问题规模由1增加到N。所以，每次增加规模时，必须先确定该点是否在圆内，若不在，则扩展。并以当前点为其中之一点，然后在P1,P2,....P（I-1）枚举另外两点。

这个算法是使用了随机化改进的。复杂度可能达到O（N）。

#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[1200];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])-eps>cir.r){            cir.cent=p[i]; cir.r=0;            for(int j=0;j<i;j++){                if(dist(cir.cent,p[j])-eps>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])-eps>cir.r){                        cir=triangleCircle(p[i],p[j],p[k]);                    }                }            }            }        }    }}int main(){    while(scanf("%d%d%d",&X,&Y,&n)!=EOF){        for(int i=0;i<n;i++){            scanf("%lf%lf",&p[i].x,&p[i].y);        }        slove();        printf("(%0.1lf,%0.1lf).\n",cir.cent.x,cir.cent.y);        printf("%0.1lf\n",cir.r);    }    return 0;}

　　


联系
我们