題目鏈接: A.Weird Flecks, But OK

題解

從XOY、YOZ、XOZ三個面，尋找最小圓覆蓋，只要滿足存在一個面的點被圓覆蓋即可，答案就是每個面的最小圓的最小值。

代碼

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define N 5010 using namespace std; int n; double x[N],y[N],z[N]; struct node{double x,y;}b[N]; node O; double R; double sqr(double x){return x*x;} double dis(node x,node y) {return sqrt(sqr(x.x-y.x)+sqr(x.y-y.y)); } bool incircle(node x) {if(dis(O,x)<=R) return true;return false; } node solve(double a,double b,double c,double d,double e,double f) {double y=(f*a-c*d)/(b*d-e*a);double x=(f*b-c*e)/(a*e-b*d);return (node){x,y}; } double f(int flag) {int i,j,k;if(flag==0){for(i=1;i<=n;i++) b[i].x=x[i],b[i].y=y[i];}if(flag==1){for(i=1;i<=n;i++) b[i].x=x[i],b[i].y=z[i];}if(flag==2){for(i=1;i<=n;i++) b[i].x=y[i],b[i].y=z[i];}random_shuffle(b+1,b+n+1);R=0;for(i=1;i<=n;i++)if(!incircle(b[i])){O.x=b[i].x;O.y=b[i].y;R=0;for(j=1;j<i;j++)if(!incircle(b[j])){O.x=(b[i].x+b[j].x)/2;O.y=(b[i].y+b[j].y)/2;R=dis(O,b[i]);for(k=1;k<j;k++)if(!incircle(b[k])){O=solve(b[i].x-b[j].x,b[i].y-b[j].y,(sqr(b[j].x)+sqr(b[j].y)-sqr(b[i].x)-sqr(b[i].y))/2,b[i].x-b[k].x,b[i].y-b[k].y,(sqr(b[k].x)+sqr(b[k].y)-sqr(b[i].x)-sqr(b[i].y))/2 );R=dis(b[i],O);}}}return R; } int main() {scanf("%d",&n);int i,j,k;for(i=1;i<=n;i++) cin >> x[i] >> y[i] >> z[i];double ans=0x3f3f3f3f;ans=min(ans,f(0));ans=min(ans,f(1));ans=min(ans,f(2));printf("%.6lf\n",ans*2); }

總結(jié)

以上是生活随笔為你收集整理的2021年度训练联盟热身训练赛第一场 A.Weird Flecks, But OK (最小覆盖圆)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。