2328.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2328 on 2006-08-20 at 23:01:35 */ 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 1024;
const double R = 1.0;

int main()
{
	int n, T;
	double x[N], y[N];
	
	scanf("%d", &T);
	for(int t = 1; t <= T; t++) {
		scanf("%d", &n);
		for(int i = 0; i < n; i++) { scanf("%lf", &x[i]); y[i] = R; }
		sort(x, x+n);
		for(int i = 1; i < n; i++) {
			for(int j = 0; j < n-i; j++) {
				double l = hypot(x[j]-x[j+1], y[j]-y[j+1]);
				double d = sqrt(4*R*R-l*l/4);
				double a = (x[j]+x[j+1])/2 - d*(y[j+1]-y[j])/l;
				double b = (y[j]+y[j+1])/2 + d*(x[j+1]-x[j])/l;
				x[j] = a; y[j] = b;
			}
		}
		printf("%d: %.4lf %.4lf\n", t, x[0], y[0]);
	}
	
	return 0;
}