OJ Board

Code: Select all

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

double min(double a, double b) {
	return a < b ? a : b;
}

double abs(double a) {
	return a < 0 ? -a : a;
}

double pow(double a) {
	return a * a;
}

int main() {
	int n, l, w, i, leftPlaced, rightPlaced, intervals;
	int pos[2000];
	double best, ly, ry, ldist, rdist;
	double dp[1001], old[1001];
	while (scanf("%d", &n) == 1) {
		scanf("%d%d", &l, &w);
		for (i = 0; i < n; i++)
			scanf("%d", &pos[i]);
		sort(pos, pos + n);
		intervals = (n / 2) - 1;
		for (i = n - 1; i >= 0; i--) {
			copy(dp, dp + n, old);
			for (leftPlaced = 0, rightPlaced = i - leftPlaced; leftPlaced <= i; leftPlaced++, rightPlaced--) {
				if (leftPlaced > n / 2 || rightPlaced > n / 2)
					continue;
				best = -1;
				if (leftPlaced + 1 <= n / 2) {
					ly = (double) leftPlaced / intervals * l;
					ldist = abs(pos[i] - ly);
					best = ldist + old[leftPlaced + 1];
				}
				if (rightPlaced + 1 <= n / 2) {
					ry = (double) rightPlaced / intervals * l;
					rdist = sqrt(pow(w) + pow(pos[i] - ry));
					best = (best < 0) ? rdist + old[leftPlaced] : min(best, rdist + old[leftPlaced]);
				}
				dp[leftPlaced] = best;
			}
		}
		printf("%.10lf\n", dp[0]);
	}
}

Code: Select all

6
18467 15
8032
701
15724
11478
10890
8494

Code: Select all

20861.0980160517