pku2194.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define size 1100

double x[size][size], y[size][size];
int N;

int cmp(const void *a, const void *b)
{
	return *(double *)a > *(double *)b ? -1 : 1;
}

double Dis(double x1, double y1, double x2, double y2)
{
	double dx = x2 - x1, dy = y2 - y1;
	return sqrt(dx * dx + dy * dy);
}

void Calc(double x1, double y1, double x2, double y2, double *x, double *y)
{
	double dx, dy, mx, my, d1, d2, rdx, rdy;
	mx = (x1 + x2) / 2;
	my = (y1 + y2) / 2;
	d1 = Dis(mx, my, x1, y1);
	if (d1 >= 2)
	{
		*x = 0;
		*y = 0;
		return;
	} 
	d2 = sqrt(4 - d1 * d1);
	dx = mx - x1;
	dy = my - y1;
	rdx = dy * d2 / d1;
	rdy = -dx * d2 / d1;
	if (rdy < 0)
	{
		rdy = -rdy;
		rdx = -rdx;
	}
	*x = mx + rdx;
	*y = my + rdy;
}

void Solve()
{
	int i, j;
	int left, right;
	for (i = 0; i < N; i++)
	{
		scanf("%lf", &x[0][i]);
		y[0][i] = 1.0;
	}
	qsort(x[0], N, sizeof(x[0][0]), cmp);
	for (j = 0; j < N - 1; j++)
	{
		for (i = 0; i < N - j - 1; i++)
		{
			Calc(x[j][i], y[j][i], x[j][i + 1], y[j][i + 1], &x[j + 1][i], &y[j + 1][i]);
		}
	}
	printf("%.4lf %.4lf\n", x[N - 1][0], y[N - 1][0]);
}

int main()
{
	while (EOF != scanf("%d", &N) && N)
		Solve();
	return 0;
}