Submission #374280

#	Time	Username	Problem	Language	Result	Execution time	Memory
374280		ne4eHbKa	Odašiljači (COCI20_odasiljaci)	C++17	70 / 70	67 ms	8800 KiB

odasiljaci

#include <bits/stdc++.h>
using namespace std;
#ifndef _LOCAL
//#pragma GCC optimize("O3,Ofast")
#else
#pragma GCC optimize("O0")
#endif
template<typename t> inline void umin(t &a, const t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, const t b) {a = max(a, b);}
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef int8_t byte;
ll time() {return chrono::system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
#define ft first
#define sd second
#define len(f) int((f).size())
#define bnd(f) (f).begin(), (f).end()
#define _ <<' '<<
const int inf = 1e9 + 5;
const ll inf64 = 4e18 + 5;
const int md = 998244353;
namespace MD {
    void add(int &a, const int b) {if((a += b) >= md) a -= md;}
    void sub(int &a, const int b) {if((a -= b) < 0) a += md;}
    int prod(const int a, const int b) {return ll(a) * b % md;}
};

const int N = 1e3 + 5;

int p[N];
int get(int i) {return p[i] == i ? i : p[i] = get(p[i]);}
int unite(int i, int j) {p[i = get(i)] = j = get(j); return i != j;}

vector<pair<ll, pii>> e;

void solve() {
    int n;
    cin >> n;
    if(n == 1) return void(cout << "0\n");
    int x[n], y[n];
    for(int i = 0; i < n; ++i) cin >> x[i] >> y[i];
    auto sq = [] (const ll f) {return f * f;};
    e.clear();
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < i; ++j)
            e.push_back({sq(x[i] - x[j]) + sq(y[i] - y[j]), {i, j}});
    sort(bnd(e));
    iota(p, p + n, 0);
    int cnt = n - 1;
    for(auto &i : e)
        if(!(cnt -= unite(i.sd.ft, i.sd.sd)))
            return void(cout << sqrt(ld(i.ft)) / 2 << endl);
}

signed main() {
    cout.precision(8); cout << fixed;
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifndef _LOCAL
//    freopen("file.in", "r", stdin);
//    freopen("file.out", "w", stdout);
#else
    system("color a");
    freopen("in.txt", "r", stdin);
    int t; cin >> t;
    while(t--)
#endif
    solve();
}

• Subtask 1: 70 / 70