?? pku2253.cpp
字號(hào):
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
typedef struct
{
int dis;
int owner[2];
} Dis;
Dis d[40000];
int n;
int point[200][2];
int status[200];
int cmp(const void *a, const void *b)
{
Dis *ap = (Dis *)a;
Dis *bp = (Dis *)b;
return ap->dis - bp->dis;
}
double calc()
{
int i, j, k;
for (i = 0; i < n; i++)
{
status[i] = i;
}
for (i = 0, j = 0; j < n - 1; j++)
{
for (k = j + 1; k < n; k++)
{
d[i].dis = (point[j][0] - point[k][0]) * (point[j][0] - point[k][0])
+ (point[j][1] - point[k][1]) * (point[j][1] - point[k][1]);
d[i].owner[0] = j;
d[i].owner[1] = k;
i++;
}
}
qsort(d, (n - 1) * n / 2, sizeof(d[0]), cmp);
for (i = 0; 1 ; i++)
{
int pa = status[d[i].owner[0]];
int pb = status[d[i].owner[1]];
if (pa != pb)
{
for (j = 0; j < n; j++)
{
if (status[j] == pb)
{
status[j] = pa;
}
}
}
if (status[1] == status[0])
{
break;
}
}
return sqrt(d[i].dis);
}
int main()
{
int i, t;
t = 0;
while (scanf("%d", &n) != -1 && n!=0)
{
for (i = 0; i < n; i++)
{
scanf("%d %d", &point[i][0], &point[i][1]);
}
t++;
printf("Scenario #%d\nFrog Distance = %.3lf\n\n", t, calc());
}
return 0;
}
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -