LYDSY 2429

题目大意

暂无

题目解法

暂无

RTFC

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
int fa[1010], X[1010], Y[1010], monkeys[510], m, n, ecnt, ans1;
double ans2;
int Find(int x) { return fa[x] == -1 ? x : fa[x] = Find(fa[x]); }
struct edge
{
    int u, v;
    double l;
    bool operator<(const edge &rhs) const { return l < rhs.l; }
} edges[1000010];
int main()
{
    memset(fa, -1, sizeof(fa));
    scanf("%d", &m);
    for (int i = 0; i < m; i++) scanf("%d", monkeys + i);
    sort(monkeys, monkeys + m);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", X + i, Y + i);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < i; j++, ecnt++)
            edges[ecnt].u = i, edges[ecnt].v = j, edges[ecnt].l =
                                                      sqrt((X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j]));
    sort(edges, edges + ecnt);
    for (int i = 0, fx, fy; i < ecnt; i++)
        if ((fx = Find(edges[i].u)) != (fy = Find(edges[i].v)))
        {
            fa[fx] = fy;
            ans1++, ans2 = edges[i].l;
            if (ans1 == n - 1) break;
        }
    printf("%d", int(monkeys + m - lower_bound(monkeys, monkeys + m, ans2)));
    return 0;
}