记录编号	104989	评测结果	AAAAAAAAAA
题目名称	[BOI2005]还原多边形	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.022 s
提交时间	2014-06-10 22:11:11	内存使用	0.33 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
//题解:圆内接
const double pi=3.141592653589793238462643383279502884;
const double eps=1e-12;
const int SIZEN=1010;
int N;
double a[SIZEN]={0};
double rho[SIZEN]={0};//极角
double R,suma=0;
bool flag;
bool cmp(double a,double b){return a>b;}
void answer(void){
	for(int i=1;i<=N;i++){
		printf("%.12lf %.12lf\n",R*cos(rho[i]),R*sin(rho[i]));
	}
}
int place(double R,bool flag){//(0,0)处放一个半径为R的圆
	//flag=0代表圆心在内,flag=1代表圆心在外
	//返回-1说明圆太小,0说明刚好,1说明太大
	rho[1]=0.0;
	double alpha;
	for(int i=1;i<=N;i++){
		//如果这条边对应的圆心角为2alpha,那么sin(alpha)=a[i]/2R
		//if(a[i]/(2.0*R)>1.0) return -1;//圆根本放不下
		alpha=asin(a[i]/(2.0*R));
		rho[i+1]=rho[i]+2.0*alpha;
		if(i==1&&flag) rho[i+1]=2.0*pi-rho[i+1];
	}
	if(rho[N+1]>2*pi+eps) return flag?1:-1;
	if(rho[N+1]<2*pi-eps) return flag?-1:1;
	return 0;
}
void find(double l,double r){
	if(r-l<eps) return;
	double mid=(l+r)/2.0;
	int sgn=place(R=mid,flag);
	if(sgn==0) return;
	if(sgn==-1) find(mid,r);
	if(sgn==1) find(l,mid);
}
void read(void){
	scanf("%d",&N);
	for(int i=1;i<=N;i++) scanf("%lf",&a[i]),suma+=a[i];
	sort(a+1,a+1+N,cmp);
}
int main(){
	freopen("boi2005_poly.in","r",stdin);
	freopen("boi2005_poly.out","w",stdout);
	read();
	if(2.0*a[1]>=suma){
		printf("NO SOLUTION\n");
		return 0;
	}
	flag=place(a[1]/2.0,0)>0;//为了检测圆心在内还是在外只需要做一次这样的判断
	//如果圆心在外,那么其他点都在劣弧上,因此以最长边为直径的圆一定过大
	//如果圆心在内,这个圆就一定过小
	//如果正好的话......当我什么也没说
	R=a[1];
	while(place(R,flag)<0) R*=2.0;
	//这道题需要用这种奇怪的方法找出枚举上界,否则在巨大的R面前各极角都被舍入误差忽略掉了,从而硬是把边凑到了一起......
	find(R/2.0,R);
	answer();
	return 0;
}