狗狗40题搞完纪念 » 1016

1016
1016.cpp


#include <cmath>
#include <cstdio>
#include <algorithm>

using namespace std;

struct Point {
	double x, y;
	Point() { }
	Point(double x, double y) : x(x), y(y) { }
};

double intersection(const Point& a, const Point& b, const Point& c, const Point& d) {
	double s1 = (b.x - a.x) * (d.y - c.y) - (b.y - a.y) * (d.x - c.x);
	double s2 = (d.x - a.x) * (d.y - c.y) - (d.y - a.y) * (d.x - c.x);
	return fabs(s1) < 1e-8 || s2 / s1 > 1e-8 ? -1e100 : s2 / s1;
}

int main() {
	int re, n, w, h;
	Point a[32], b[32];
	double l[32][32], r[32][32], s[32], dp[4096];

	scanf("%d", &re);
	for (int ri = 1; ri <= re; ++ri) {
		scanf("%d%d%d", &w, &h, &n);
		for (int i = 0; i < n; ++i) {
			scanf("%lf%lf", &a[i].x, &a[i].y);
			if (i > 0) {
				b[i] = a[i - 1];
			}
		}
		b[0] = a[n - 1];
		a[n] = b[n + 3] = Point(0, 0);
		a[n + 1] = b[n] = Point(0, h);
		a[n + 2] = b[n + 1] = Point(w, h);
		a[n + 3] = b[n + 2] = Point(w, 0);

		for (int i = 0; i < n; ++i) {
			s[i] = hypot(b[i].x - a[i].x, b[i].y - a[i].y);
			for (int j = 0; j < n; ++j) {
				if (i == j) {
					continue;
				}
				l[i][j] = intersection(a[i], b[i], a[j], b[j]);
				r[i][j] = intersection(b[i], a[i], a[j], b[j]);
			}
			l[i][i] = r[i][i] = -1e100;
			for (int j = n; j < n + 4; ++j) {
				l[i][i] = max(l[i][i], intersection(a[i], b[i], a[j], b[j]));
				r[i][i] = max(r[i][i], intersection(b[i], a[i], a[j], b[j]));
			}
		}

		fill(dp, dp + (1 << n), 1e100);
		dp[0] = 0;
		for (int i = 0; i < (1 << n); ++i) {
			for (int j = 0; j < n; ++j) {
				if ((i & (1 << j)) != 0) {
					continue;
				}
				double ll = l[j][j], rr = r[j][j];
				for (int k = 0; k < n; ++k) {
					if ((i & (1 << k)) != 0) {
						ll = max(ll, l[j][k]);
						rr = max(rr, r[j][k]);
					}
				}
				dp[i ^ (1 << j)] = min(dp[i ^ (1 << j)], dp[i] + (1 - ll - rr) * s[j]);
			}
		}

		if (ri > 1) {
			puts("");
		}
		printf("Minimum total length = %.3lf\n", dp[(1 << n) - 1]);
	}

	return 0;
}

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
//334 	2010-06-27 22:26:51 	Accepted 	1016 	C++ 	10 	180 	anotherpeg 	Source
Leave a Reply