제출 #374282

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
374282		NONAME	Odašiljači (COCI20_odasiljaci)	C++17	70 / 70	244 ms	552 KiB

odasiljaci

#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int man = 1000;

int n;
int pr[man];
long long a[man], b[man];

long long sq(long long x) {
    return x * x;
}

long long rast(int i, int j) {
    return sq(a[i] - a[j]) + sq(b[i] - b[j]);
}

int f(int x) {
    return (x == pr[x]) ? x : pr[x] = f(pr[x]);
}

void un(int x, int y) {
    x = f(x);
    y = f(y);
    pr[y] = x;
}

bool can(long long x) {
    for (int i = 0; i < n; ++i) {
        pr[i] = i;
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (x >= rast(i, j)) {
                un(i, j);
            }
        }
    }

    set <int> s;
    for (int i = 0; i < n; ++i) {
        s.insert(f(i));
    }
    return (int)(s.size()) == 1;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
    }

    long long l = 0, r = 2e18;
    while (l < r) {
        long long md = (l + r) >> 1LL;
        if (can(md) == true) {
            r = md;
        } else {
            l = md + 1;
        }
    }

    long long ans = (sqrt(l) / (long double)(2)) * 1e7;

    string t = to_string(ans);

    while ((int)(t.size()) < 8) {
        t = "0" + t;
    }
    for (int i = 0; i < (int)(t.size()); ++i) {
        if ((i + 7) == (int)(t.size())) {
            cout << '.';
        }
        cout << t[i];
    }
    cout << "\n";

    return 0;
}

• Subtask 1: 70 / 70