细节参见代码:
#include<cstdio>
include<cstring>
include<algorithm>
include<iostream>
include<string>
include<vector>
include<stack>
include<bitset>
include<cstdlib>
include<cmath>
include<set>
include<list>
include<deque>
include<map>
include<queue>
define Max(a,b) ((a)>(b)?(a):(b))
define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps = 1e-9, PI = 3.1415926535897932384626433832795;
const int mod = 1000000000 + 7;
const int INF = int(1e9);
// & 0x7FFFFFFF
const int seed = 131;
const ll INF64 = ll(1e18);
const int maxn = 200 + 10;
int T,n,m,cnt,p[maxn],kase=0;
double ans[maxn][maxn],x[maxn],y[maxn];
struct node {
int a, b;
double dist;
node(int a=0, int b=0, double dist=0):a(a), b(b), dist(dist) {}
bool operator < (const node& rhs) const {
return dist < rhs.dist;
}
}a[maxnmaxn];
vector<node> g[maxn];
int _find(int x) { return p[x] == x ? x : p[x] = _find(p[x]); }
void dfs(int u, int fa) {
int len = g[u].size();
for(int i=0;i<len;i++) {
int v = g[u][i].a;
if(v != fa) {
ans[1][v] = max(ans[1][u], g[u][i].dist);
dfs(v, u);
}
}
}
double solve() {
for(int i=1;i<=n;i++) p[i] = i, g[i].clear();
sort(a, a+cnt);
for(int i=0;i<cnt;i++) {
int x = _find(a[i].a);
int y = _find(a[i].b);
if(x != y) {
p[x] = y;
g[a[i].a].push_back(node(a[i].b, 0, a[i].dist));
g[a[i].b].push_back(node(a[i].a, 0, a[i].dist));
}
}
ans[1][1] = -1.0;
dfs(1, 1);
return ans[1][2];
}
int main() {
while(~scanf("%d",&n) && n) {
for(int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);
cnt = 0;
for(int i=1;i<=n;i++) {
for(int j=i+1;j<=n;j++) {
double cur = sqrt((x[i] - x[j])(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]));
a[cnt++] = node(i,j,cur);
}
}
printf("Scenario #%d\n",++kase);
printf("Frog Distance = %.3f\n\n",solve());
}
return 0;
}</pre>
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。