Submission #374277

#	Time	Username	Problem	Language	Result	Execution time	Memory
374277		NONAME	Odašiljači (COCI20_odasiljaci)	C++17	70 / 70	240 ms	512 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;
        }
    }

    cout.precision(8); cout << fixed;
    cout << (sqrt(l) / (long double)(2)) << "\n";

    return 0;
}

• Subtask 1: 70 / 70