在正多边形内部有一点,给出该点到多边形各点的距离,求正多边形的边长
从正多边形的定义出发,各边相等各角也相等的多边形,直接二分答案 , 枚举边长 , 满足各边所对角的和为2*pi的即可能为答案 ,此时再判断一下多边型各角是否相等即可,出现impossible的情况有2种 , 一个是二分搜不到满足条件的边长 ,一个是搜到边不满足角相等,因为三角形2边确定,则夹角所对边和夹角都是单调递增。
#include <cstdio> #include <cmath> const double pi=acos(-1.0); const double eps=1e-6; const int maxn=105; double dis[maxn]; int n; double Acos(double a , double b , double c) { return acos((a*a+b*b-c*c)/(2*a*b)); } bool Isregular(double x) { double tmp=Acos(x,dis[0],dis[n-1])+Acos(x,dis[0],dis[1]); for (int i=1 ; i<n ; ++i) { //printf("%lf ==%lf %lf\n",tmp , Acos(x,dis[i],dis[i-1])) if(fabs(tmp-Acos(x,dis[i],dis[i-1])-Acos(x,dis[i],dis[i+1]))>eps)return false; } return true; } int main () { int cas; scanf("%d",&cas); for (int I=1 ; I<=cas ; ++I) { scanf("%d",&n); for (int i=0 ; i<n ; ++i) { scanf("%lf",dis+i); } dis[n]=dis[0]; bool flag=false; double ans; double low=0.0 ,high=20005.0; while (fabs(high-low)>eps) { double mid=(low+high)/2; double delta=0.0; for (int i=0 ; i<n ; ++i) { delta += Acos(dis[i] , dis[i+1] , mid); } if(fabs(delta-2*pi)<eps) { { ans=mid; flag=true; break; } } if(delta<2*pi)low=mid; else high=mid; } if(flag && Isregular(ans))printf("Case %d: %0.3lf\n" , I , ans); else printf("Case %d: impossible\n",I); } return 0; }