比賽時沒做出來，最后10 鐘時倒是想枚舉每個角度，精度估計上可能會出問題；

后來聽“理寶”說可以暴力枚舉邊的長度，精確到0.001，數(shù)據(jù)恰好10^7，T_T~~

vongang說可以用二分做，也就是官方解題報告的解法：

這題用二分的關(guān)鍵是：

? ? ? ? 首先Regular Polygon是正多邊形，：

? ? ? ? 想到邊長和所對的角成正比，沒想到啊，Orz，各路大神

貼個山寨的代碼吧：

#include<stdio.h>
#include<math.h>

#define N 110
const double inf =10000;
const double pi=acos(-1.0);
const double eps =1e-6;
double len[N];

bool dd(double x,double y) {return fabs(x-y)<eps;}
bool xy(double x,double y) {return x < y - eps;}
bool yx(double x,double y) {return x > y + eps;}
bool xyd(double x,double y) {return x < y + eps;}
bool yxd(double x,double y) {return x > y - eps;}

double ang_cal(double a,double b,double c)
{
return acos((a*a+b*b-c*c)/(2*a*b));
}
int solve(int n,double x)
{
double ang=0;
for(int i=0;i<n;i++)
{
if(yxd(x,len[i]+len[i+1])) return 1;
if(xyd(x,fabs(len[i]-len[i+1]))) return -1;
ang+=ang_cal(len[i],len[i+1],x);
}
if(dd(ang,2*pi)) return 0;
if(xy(ang,2*pi)) return -1;
if(yx(ang,2*pi)) return 1;
}
bool check(double ang,double x)
{
double a1=ang_cal(len[1],x,len[0]);
double a2=ang_cal(len[1],x,len[2]);
return dd(ang,a1+a2);
}

int main()
{
int cs=1,ncs,n;
scanf("%d",&ncs);
while(ncs--)
{
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%lf",len+i);
len[n]=len[0];

double bg=0,end=inf,mid;
int flag=0,cnt=0;
while( xyd(bg,end) )
{
if(dd(bg,end)) cnt++;
if(cnt==2) break;

mid=(bg+end)/2;
int ans=solve(n,mid);
if(ans==0)
{
flag=1;break;
}
if(ans > 0) end=mid;
else bg=mid;
}
if(flag)
{
double ang=(n-2)*pi/n;
if(!check(ang,mid))
printf("Case %d: impossible\n",cs++);

else
printf("Case %d: %.3f\n",cs++,mid);
}
else printf("Case %d: impossible\n",cs++);
}
return 0;
}

轉(zhuǎn)載于:https://www.cnblogs.com/skyming/archive/2012/04/05/2433683.html

總結(jié)

以上是生活随笔為你收集整理的HDU 4033Regular Polygon(二分+高精度）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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