oj.uz

Submission #374274

# Submission time Handle Problem Language Result Execution time Memory
374274 2021-03-07T06:04:10 Z kartel Odašiljači (COCI20_odasiljaci) C++14
42 / 70
 796 ms 4608 KB 
#include <bits/stdc++.h>
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
//#include <time.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
#define F first
#define S second
#define pb push_back
//#define M ll(1e9 + 7)
#define M ll(998244353)
#define sz(x) (int)x.size()
#define re return
#define oo ll(1e18)
#define el '\n'
#define pii pair <int, int>
#define all(x) (x).begin(), (x).end()
#define arr_all(x, n) (x + 1), (x + 1 + n)
#define vi vector<int>
#define eps (ld)1e-7
using namespace std;
typedef long long ll;
//using namespace __gnu_pbds;
//typedef tree <ll, null_type, less_equal <ll> , rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef double ld;
typedef unsigned long long ull;
typedef short int si;

const int N = 1e3 + 50;

vector <int> g[N];
bool mk[N];
int x[N], y[N];
int n;

void dfs(int v) {
    if (mk[v]) {
        return;
    }
    mk[v] = 1;

    for (auto u : g[v]) {
        dfs(u);
    }
}

ld d(int i, int j) {return (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);}

bool gd(ld R) {
    for (int i = 1; i <= n; i++) {
        g[i].clear();
        mk[i] = 0;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (d(i, j) < 4 * R * R + eps) {
                g[i].pb(j);
                g[j].pb(i);
            }
        }
    }

    dfs(1);

    int i = 1;
    while (i <= n && mk[i]) {
        i++;
    }

    return (i > n);
}

int main()
{
//    mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());;
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	in("toys.in");
//	out("toys.out");
//    in("input.txt");
//    out("output.txt");
//    cerr.precision(9); cerr << fixed;

//    clock_t tStart = clock();

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }

    ld l = 0;
    ld r = 1e18;

    while (l + eps < r) {
        ld md = (l + r) / (ld)2;

        if (gd(md)) {
            r = md;
        }
        else {
            l = md + eps;
        }
    }

    cout << setprecision(6) << fixed << l;
}


/*

7
4 6 7 2 3 1 5
*/

Subtask #1
42.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 3 ms 364 KB Output is correct
4 Incorrect 5 ms 364 KB Output isn't correct
5 Incorrect 7 ms 492 KB Output isn't correct
6 Correct 154 ms 1516 KB Output is correct
7 Correct 145 ms 1516 KB Output is correct
8 Correct 314 ms 3436 KB Output is correct
9 Incorrect 780 ms 4608 KB Output isn't correct
10 Incorrect 796 ms 4588 KB Output isn't correct