首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。