Regular Polygon

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65768/65768 K (Java/Others)

Total Submission(s): 2203    Accepted Submission(s): 682

Problem Description

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.

Input

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.

Output

For the ith case, output one line “Case k: ” at first. Then for every test case, if there is such a regular polygon exist, output the side's length rounded to three digits after the decimal point, otherwise output “impossible”.

Sample Input

2

3

3.0 4.0 5.0

3

1.0 2.0 3.0

Sample Output

Case 1: 6.766

Case 2: impossible

Source

 解题报告：这道题的题意就是在多边形的内部有一个点，点到达各个顶点的距离已知，求有这样的正多边形吗；思路，是把多边形分成N个三角形，多边形的边长一定满足三角形定理，min（两边之和）> 正多边形的边长> max(两边之差)；在利用二分法枚举正多边形的边，直到枚举的便满足内角和为360即可，利用余弦定理求角的大小：cosA = (a* a + b * b - c * c) / 2 * a * b;

代码如下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const double PI = acos(-1.0);const int MAX = 105;const double eps = 1e-8;double edge[MAX];int T, N;int main(){    int i, flag, k;    double min, max, ans, radian;    scanf("%d", &T);    for (k = 1; k <= T; ++k)    {        memset(edge, 0, sizeof(edge));        scanf("%d", &N);        for (i = 0; i < N; ++i)        {            scanf("%lf", &edge[i]);        }        edge[N] = edge[0];        max = 999999999;        min = -20;        double temp;        for (i = 1; i <= N; ++i)        {            temp = edge[i] + edge[i - 1];            //利用了三角形定理，两边之和大于第三边，两边之差小于第三边            if (max > temp)//找到两边相加的最小            {                max = temp;            }            temp = fabs(edge[i] - edge[i - 1]);            if (min < temp)//找到两边相减的最大            {                min = temp;            }        }        double mid;        flag = 0;        while (max - min > eps)//利用二分法，枚举        {            mid = (max + min) / 2.0;            radian = 0;//弧度            for (i = 1; i <= N; ++i)            {                //利用余弦定理求弧度                radian += acos((edge[i] * edge[i] + edge[i - 1] * edge[i - 1] - mid * mid) / (2.0 * edge[i] * edge[i - 1]));            }            if (fabs(radian - 2.0 * PI) < eps)//存在的时候            {                flag = 1;                ans = mid;                break;            }            else if (radian - 2 * PI > eps)//枚举的边大的            {                max = mid;            }            else//枚举的边小的时候            {                min = mid;            }        }        printf("Case %d: ", k);        if (flag)        {            printf("%.3lf\n", ans);        }        else        {            printf("impossible\n");        }    }    return 0;}