Getting in Line

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
2.1 kB
3
Indexable
Never
#include<stdio.h>
#include<cmath>
#include<algorithm>
using namespace std;

typedef long long ll;

int vis[1 << 10][15][15];
double dp[1 << 10][15][15];
int x[15];
int y[15];
int parent[1 << 10][15][15];
int n;
int st;


double distance(int i, int j) {
	double diff_x = (double)x[i] - x[j];
	double diff_y = (double)y[i] - y[j];
	return sqrt(diff_x * diff_x + diff_y * diff_y);
}

bool checkbit(int bt, int i) {
	if (bt & (1 << i)) {
		return false;
	}
	return true;
}

int setbit(int bt, int i) {
	bt = bt | (1 << i);
	return bt;
}

double get_in_line(int bt, int end) {
	if (bt == (1 << n) - 1)return 0;

	if (vis[bt][end][st]) return dp[bt][end][st];

	double mn = 1e9;
	int ml =1e9;
	for (int i = 0;i < n;i++) {
		if (checkbit(bt, i)) {
			//printf("%d %d %d\n", bt, i, setbit(bt, i));
			double ans = get_in_line(setbit(bt, i), i) + distance(end, i);
			if (mn > ans) ml = i;
			mn = min(ans, mn);
		}
	}
	vis[bt][end][st] = 1;
	parent[bt][end][st] = ml;
	return dp[bt][end][st] = mn;
}

void print(int bt, int end) {
	if (bt == (1 << n) - 1) return;
	printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2lf feet.\n", x[end], y[end], x[parent[bt][end][st]], y[parent[bt][st][end]], distance(end, parent[bt][st][end]) + 16);
	print(setbit(bt, parent[bt][st][end]), parent[bt][st][end]);
}

int main() {
	int cnt = 0;
	while (scanf("%d", &n) and n) {
		for (int i = 0;i < n;i++) {
			scanf("%d %d", &x[i], &y[i]);
		}

		for (int i = 0;i < 260;i++) {
			for (int j = 0;j < 10;j++) {
				for (int k = 0;k < 10;k++) {
					vis[i][j][k] = 0;
				}
			}
		}
		double mn = 1e9;
		int start = 0;
		for (int i = 0;i < n;i++) {
			st = i;
			double ans = get_in_line((1 << st), st);
			if (mn > ans) start = st;
			mn = min(ans, mn);
		}
		st = start;
		printf("**********************************************************\n");
		printf("Network #%d\n", ++cnt);
		print((1 << st), st);
		printf("Number of feet of cable required is %.2lf.\n", mn + (n - 1) * 16.0);
	}
}