1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
| #include <bits/stdc++.h> #define FOE(i, s, t) for (int i = s; i <= t; i++) #define FOR(i, s, t) for (int i = s; i < t; i++) #define K 601 #define M 1000000007 #define LL long long using namespace std; int n; int x[K], y[K]; double dist(int id1, int id2) { double dx = abs(x[id1] - x[id2]); double dy = abs(y[id1] - y[id2]); return sqrt(dx * dx + dy * dy); } int ok[K][K][2]; double dp[K][K][2]; int has[K][K]; int prev(int u) { return (u == 1 ? n : u - 1); } int nxt(int u) { return (u == n ? 1 : u + 1); } double solve2(int sta, int fin, int dir) { if (sta == fin) return 0.00; if (ok[sta][fin][dir] == 0) { dp[sta][fin][dir] = 0.00; ok[sta][fin][dir] = 1; if (dir == 1) { for (int i = nxt(sta); i != fin; i = nxt(i)) { if (has[sta][i]) { dp[sta][fin][dir] = max(dp[sta][fin][dir], max(solve2(i, fin, 1), solve2(i, sta, 0)) + dist(sta, i)); } } } else { for (int i = prev(sta); i != fin; i = prev(i)) { if (has[sta][i]) { dp[sta][fin][dir] = max(dp[sta][fin][dir], max(solve2(i, fin, 0), solve2(i, sta, 1)) + dist(sta, i)); } } } } return dp[sta][fin][dir]; } void solve() { scanf("%d", &n); FOE(i, 1, n) scanf("%d%d", &x[i], &y[i]); FOE(i, 1, n) FOE(j, 1, n) ok[i][j][0] = ok[i][j][1] = 0; double ret = 0.00; FOE(i, 1, n) FOE(j, 1, n) has[i][j] = 0; int m; scanf("%d", &m); FOE(i, 1, m) { int u, v; scanf("%d%d", &u, &v); has[u][v] = has[v][u] = 1; } FOE(i, 1, n) FOE(j, 1, n) if (has[i][j]) { double temp = max(solve2(j, i, 1), solve2(j, i, 0)) + dist(i, j); if (temp > ret) ret = temp; } printf("%.9f\n", ret); } int main() { int t; scanf("%d", &t); while (t--) solve(); }
|