Regular Polygon
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 2515 Accepted Submission(s): 782
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
1 //给定一个正num边型内一点距离所有点的距离，求边长。如果无解输出impossible 2 //所有角度和是否为2*PI，大于则缩小边，否则扩大边 3 #include <cstdio> 4 #include <iostream> 5 #include <cstring> 6 #include <cmath> 7 using namespace std; 8 9 double ch[200]; 10 const double PI = 4 * atan( double( 1 ) ); 11 //const double PI = 3.1415926;//这个wa 12 int num; 13 14 double is_triangle( double a, double b, double c ) 15 { 16 if( c > a + b ) 17 return 100; 18 else if( c < fabs( a - b ) ) 19 return -100; 20 else 21 return acos( ( a * a + b * b - c * c ) / ( 2 * a * b ) ); 22 } 23 24 double Acos( double a, double b, double c ) 25 { 26 return is_triangle( a, b, c ); 27 } 28 29 double total_angle( double mid ) 30 { 31 double ans = 0; 32 for( int i = 2; i <= num; ++i ) 33 { 34 double t = Acos( ch[i], ch[i-1], mid ); 35 if( fabs( t ) == 100 ) // 如果mid的这个取值使得某些相邻的两条边不 36 return t; // 能够形成三角形，则及时退出 37 else 38 ans += Acos( ch[i], ch[i-1], mid ); 39 } 40 return ans; 41 // 最后返回总的角度大小 42 } 43 44 double Bsearch( double ss, double ee ) 45 { 46 double left = ss, right = ee, mid, sum_angle; 47 while( right - left >= 1e-9 ) 48 { 49 mid = ( left + right ) / 2.0; 50 double t = total_angle( mid ); // 计算出一部分的角度总和 51 if( fabs( t ) == 100 ) 52 { 53 if( t > 0 ) 54 right = mid;//缩小边 55 else 56 left = mid;//扩大边 57 } 58 else 59 { 60 sum_angle = t + Acos( ch[1] , ch[num], mid ); 61 if( sum_angle - 2 * PI > 1e-9 ) 62 right = mid; 63 else if( sum_angle - 2 * PI < -1e-9 ) 64 left = mid; 65 else 66 return mid; 67 } 68 } 69 return 0; 70 } 71 72 int main( ) 73 { 74 int i,j,k,T; 75 cin>>T; 76 for(i = 1; i <= T; ++i ) 77 { 78 cin>>num; 79 for(j = 1; j <= num; ++j ) 80 cin>>ch[j]; 81 // 接下来选择第num条边以及第1条边来二分答案 82 // 根据三角形中有 C < A+B && C > A-B; 83 double ans = Bsearch( fabs( ch[num] - ch[1] ), ch[1] + ch[num] ); 84 printf( "Case %d: ", i ); 85 if( ans == 0 ) 86 puts( "impossible" ); 87 else 88 printf( "%.3lf\n", ans ); 89 } 90 return 0; 91 }