oj.uz

Submission #701146

# Submission time Handle Problem Language Result Execution time Memory
701146 2023-02-20T08:45:21 Z Chal1shkan Odašiljači (COCI20_odasiljaci) C++14
70 / 70
 227 ms 4584 KB 
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <cmath>
#include <set>
#include <unordered_map>
#include <numeric>
#include <vector>

# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())
# define deb(x) cerr << #x  << " = " << x << endl; 

typedef long long ll;
typedef unsigned long long ull;
typedef double ld;

const ll maxn = 1e3 + 25;
const ll inf = 3e9 + 0;
const ll mod = 1e9 + 7;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};
const ld eps = 1e-7;

using namespace std;

int n;
pair <ld, ld> p[maxn];
struct DSU
{
    int par[maxn];
    DSU ()
    {
        iota(par, par + maxn, 0);
    }
    int find_set (int v)
    {
        if (v == par[v]) return v;
        return v = find_set(par[v]);
    }
    bool union_sets (int u, int v)
    {
        u = find_set(u);
        v = find_set(v);
        if (u == v) return 0;
        par[v] = u;
        return 1;
    }
} zxc;

ld dist (pair <ld, ld> q, pair <ld, ld> w)
{
    return (ld)sqrt((q.ff - w.ff) * (q.ff - w.ff) + (q.ss - w.ss) * (q.ss - w.ss));
}

bool cmp (pair <int, int> x, pair <int, int> y)
{
    return dist(p[x.ff], p[x.ss]) < dist(p[y.ff], p[y.ss]);
}

void ma1n (/* SABR */) 
{
    cin >> n;    
    for (int i = 1; i <= n; ++i)
    {
        cin >> p[i].ff >> p[i].ss;
    }
    vector <pair <int, int> > g;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = i + 1; j <= n; ++j)
        {
            g.pb({i, j});
        }
    }
    sort(g.begin(), g.end(), cmp);
    ld ans = 0;
    for (int i = 0; i < sz(g); ++i)
    {
        if (zxc.union_sets(g[i].ff, g[i].ss))
        {
            ans = dist(p[g[i].ff], p[g[i].ss]);
        }
    }
    cout << fixed << setprecision(8) << ans / 2 - eps;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//  freopen("file.in", "r", stdin);
//  freopen("file.out", "w", stdout);
    int ttt = 1;
//  cin >> ttt;
    for (int test = 1; test <= ttt; ++test)
    {
//      cout << "Case " << test << ":" << ' ';
        ma1n();
    }
    return 0;
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 40 ms 1480 KB Output is correct
7 Correct 39 ms 1492 KB Output is correct
8 Correct 93 ms 4556 KB Output is correct
9 Correct 217 ms 4584 KB Output is correct
10 Correct 227 ms 4568 KB Output is correct