# Getting in Line

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);
}
}