比赛时悲剧的没做出来,赛后终于解决了,革命尚未成功,同志仍需努力呀!
#include <iostream> #include <math.h> #include <stdio.h> using namespace std; const int N=102; double pi=acos(-1); const double eps=1e-8; double dis[N]; int n; double solve (double l,double r) { if(fabs(l-r)<eps)return -1; double mid=(l+r)/2; int i; double ang=0; for(i=0;i<n;i++) { if(mid-(dis[i]+dis[i+1])>eps)return solve(l,mid);//边太大,构不成三角形 if(mid-fabs(dis[i]-dis[i+1])<eps)return solve(mid,r);//边太小,构不成三角形 double cs=(dis[i]*dis[i]+dis[i+1]*dis[i+1]-mid*mid)/(2*dis[i]*dis[i+1]); ang+=acos(cs); } if(fabs(ang-2*pi)<eps)return mid;//等于360度 else if(ang-2*pi>eps)return solve(l,mid);//大于360度,说明mid太大 else return solve(mid,r);//小于360度说明mid太小 return -1; } int main() { int t; cin>>t; int ca=1; while(t--) { cin>>n; int i; for(i=0;i<n;i++) { scanf("%lf",&dis[i]); } dis[n]=dis[0]; double ans=solve (0,20000); if(ans==-1)printf("Case %d: impossible\n",ca); else printf("Case %d: %.3lf\n",ca,ans); ca++; } return 0; } /* 2 3 3.0 4.0 5.0 3 1.0 2.0 3.0 */