学步园

终于有题我过了T T。。

刚开始JC看错题了，以为是到各边的距离，然后觉得蛮水的，直接以0 0 为内点，旋转后求垂线围成的多边形是否是正多边形即可。

后来一看是到各顶点的距离。想了一会儿。

后来用余弦定理，二分边长（边长和反余弦是单调的）判断所有构成三角形的顶角和是否为2*pi即可。

构不成三角形的话直接判断即可。注意二分最后相等也需要判的，但是一直相等找不到结果的话就要跳出了。1Y~

精度开的1e-8，测试了下，1e-6也没问题。

感谢xymscau同学的检查，代码已经改过。二分边长后需要判定角度是否为多边形的角度，否则会出现菱形的情况，比如下组数据。代码已更正在HDU依然能AC，显然数据弱了，估计标程也没考虑这个情况。。。但是只有精度开到1e-6能过，其他均不行，无语。。

4
2 1.414 4 1.414

应该输出impossible，即使构成边长和菱形长度相同的正方形，但是不存在一个这样的点满足上述边长。

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#define MID(x,y) ( ( x + y ) >> 1 )
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
#define FOR(i,s,t) for(int i=s; i<t; i++)
#define BUG puts("here!!!")
#define STOP system("pause")
#define file_r(x) freopen("x", "r", stdin)
#define file_w(x) freopen("x", "w", stdout)

using namespace std;

const int MAX = 110;
const double pi = acos(-1.0);
const double inf = 20000;
double len[MAX];
const double eps = 1e-6;
bool dy(double x,double y)	{	return x > y + eps;}	// x > y 
bool xy(double x,double y)	{	return x < y - eps;}	// x < y 
bool dyd(double x,double y)	{ 	return x > y - eps;}	// x >= y 
bool xyd(double x,double y)	{	return x < y + eps;} 	// x <= y 
bool dd(double x,double y) 	{	return fabs( x - y ) < eps;}  // x == y
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(i, 0, n)
	{
		if( dyd(x, len[i] + len[i+1]) ) return 1;	// 边长过大构不成三角形 
		if( xyd(x, fabs(len[i] - len[i+1])) ) return -1;//边长过小构不成三角形 
		double a = ang_cal(len[i], len[i+1], x);
		ang += a;
	}
	if( dy(ang, 2*pi) ) return 1;	// 角度大，也就是x过大 
	if( xy(ang, 2*pi) ) return -1;	// 角度小，也就是x过小 
	if( dd(ang, 2*pi) ) return 0;
}

bool check(int n, double ang, double x)
{
	double a1 = ang_cal(len[1], x, len[0]);
	double a2 = ang_cal(len[1], x, len[2]);
	return dd(a1+a2, ang);
}
int main()
{
	int ncases, n, ind = 1;
	
	scanf("%d", &ncases);
	
	while( ncases-- )
	{
		scanf("%d", &n);
		FOR(i, 0, n)
			scanf("%lf", &len[i]);
		
		len[n] = len[0];
		
		double begin = 0, end = inf, mid;
		bool f = false;
		int cnt = 0;
		
		while( xyd(begin, end) )
		{
			if( dd(begin, end) )
				cnt++;
			if( cnt == 2 ) break;	// 避免找不到死循环 
			mid = (begin + end)/2;
			int ans = solve(n, mid);
			if( ans == 0 )
			{
				f = true;
				break;
			}
			if( ans > 0 )
				end = mid;
			else
				begin = mid;
		}
		
		printf("Case %d: ",ind++);
		
		if( f )
		{
			double ang = (n-2)*pi/n;
			if( !check(n, ang, mid) )	// 检测角度是否为正多边形的角度 
			{
				printf("impossible\n");
				continue;
			}
			printf("%.3lf\n", mid);
		}
		else
			printf("impossible\n");
	}

return 0;
}