1759.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1759 on 2006-07-24 at 11:39:38 */ 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

typedef long long int64;
const int N = 10240;

inline int64 iceil(double n) { return (int64)(n+0.5); }

int main()
{
	int n, i;
	int64 h[N], dis[N] = { 0 };
	
	while(scanf("%d", &n) != EOF && n != 0) {
		for(i = 0; i < n; i++) {
			scanf("%lld", &h[i]);
			if(i > 0) dis[i] = (h[i]-h[i-1])*(h[i]-h[i-1]);
		}
		int64 unit, total = 0;
		double x;
		for(i = 2; i < n; i++) total += dis[i]*(n-i);
		for(i = 1; i < n; i++) {
			double px = (h[i]-h[i-1])*(n-i)*1.0/n+h[i-1], 
				dx = (h[i-1]-px)*(h[i-1]-px), dy = (h[i]-px)*(h[i]-px);
			int64 tdis = i*iceil(dx)+(n-i)*iceil(dy)+total;
			if(i == 1 || tdis < unit) { unit = tdis, x = px; }
			if(i != n-1) total += i*dis[i]-(n-1-i)*dis[i+1];
		}
		printf("%.3lf\n", x);
	}
	
	return 0;
}