2015
04-15

# Regular Polygon

In a 2_D plane, there is a point strictly in a regular polygon with N sides. If you are given the distances between it and N vertexes of the regular polygon, can you calculate the length of reguler polygon’s side? The distance is defined as dist(A, B) = sqrt( (Ax-Bx)*(Ax-Bx) + (Ay-By)*(Ay-By) ). And the distances are given counterclockwise.

First a integer T (T≤ 50), indicates the number of test cases. Every test case begins with a integer N (3 ≤ N ≤ 100), which is the number of regular polygon’s sides. In the second line are N float numbers, indicate the distance between the point and N vertexes of the regular polygon. All the distances are between (0, 10000), not inclusive.

First a integer T (T≤ 50), indicates the number of test cases. Every test case begins with a integer N (3 ≤ N ≤ 100), which is the number of regular polygon’s sides. In the second line are N float numbers, indicate the distance between the point and N vertexes of the regular polygon. All the distances are between (0, 10000), not inclusive.

2
3
3.0 4.0 5.0
3
1.0 2.0 3.0

Case 1: 6.766
Case 2: impossible

 Run ID Submit Time Judge Status Pro.ID Exe.Time Exe.Memory Code Len. Language Author 4584550 2011-09-11 22:00:53 Accepted 4033 15MS 280K 1051 B G++ xym2010
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
const double PI=acos(0.0)*2;
int n;
double b[105];
double angle(double a,double b,double c)
{
return acos((a*a+b*b-c*c)/2/a/b);
}
int OK(double mid)
{
double ans=0;
for(int i=0;i<n;i++)
{
if(b[i]+b[(i+1)%n]<=mid)
return -1;
if(fabs(b[i]-b[(i+1)%n])>=mid)
return 0;
ans+=angle(b[i],b[(i+1)%n],mid);
}
if(fabs(ans-2*PI)<0.000001)return 1;
else
if(ans-2*PI>0)return -1;
else
return 0;
}
int main()
{
int T,t,flag;
scanf("%d",&T);
for( t=1;t<=T;t++)
{
flag=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%lf",&b[i]);
}
double r=20000,l=0,mid;
printf("Case %d: ",t);
while(r-l>0.000001)
{
mid=(l+r)/2;
int kk=OK(mid);
if(kk==1)
{
printf("%.3f\n",mid);
flag=1;
break;
}
else
if(kk==0)
l=mid;
else
r=mid;
}
if(flag==0)printf("impossible\n");
}
return 0;
}


1. 如果两个序列的最后字符不匹配（即X [M-1]！= Y [N-1]）
L（X [0 .. M-1]，Y [0 .. N-1]）= MAX（L（X [0 .. M-2]，Y [0 .. N-1]），L（X [0 .. M-1]，Y [0 .. N-1]）
这里写错了吧。

2. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.