话说这次参加比赛, 怎一个悲剧了得, 只A了一道题……虽然是去打酱油的, 但这酱油打得也太……
开始看这题时,没有思路, 后来 就想到通过枚举其边长, 利用余弦公式求出所有角度, 还可以通过海伦公式和正多边形面积公式来求解……我先写了个通过面积来求解的, 一直得不到正确答案, 又仔细想了一下, 发现这两个公式中都用到了正多边形边长, 不一定单调, 没法用二分,于是乎,我又很快用第一种方法来写, 结果好几次都WR,扩大精度还是WR, 最后将3.1415926589改为了arcos(-1), 然后就神奇的AC了……
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; int main() { int T, n, i, j, flag; double length[101]; double left, right, mid, a, pai=2 * acos(-1.0); scanf("%d", &T); for(i=1; i<=T; i++) { left=0, right=99999999; scanf("%d %lf", &n, length); for(j=1; j<n; j++) { scanf("%lf", length+j); if(left<fabs(length[j]-length[j-1])) left=fabs(length[j]-length[j-1]); if(right>length[j-1]+length[j]) right=length[j-1]+length[j]; } if(left<fabs(length[n-1]-length[0])) left=fabs(length[n-1]-length[0]); if(right>length[n-1]+length[0]) right=length[n-1]+length[0]; flag=0; while(left<=right) { a=0; mid=(left+right)/2; for (j=0; j<n-1; j++) { a+=acos((length[j]*length[j]+length[j+1]*length[j+1]-mid*mid)/(2*length[j]*length[j+1])); } a+=acos((length[j]*length[j]+length[0]*length[0]-mid*mid)/(2*length[j]*length[0])); if( a-pai>0.0000000001) right=mid-0.0000000001; else if( a-pai<-0.0000000001) left=mid+0.0000000001; else { flag=1; break; } } if( flag ) printf("Case %d: %.3f\n", i, mid); else printf("Case %d: impossible\n", i); } }