oj.uz

Submission #922341

# Submission time Handle Problem Language Result Execution time Memory
922341 2024-02-05T12:25:35 Z Shayan86 Odašiljači (COCI20_odasiljaci) C++14
70 / 70
 117 ms 4444 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 1e3 + 50;
const ll Mod = 1e9 + 7;

ll n, x[N], y[N];

bool mark[N];
vector<int> adj[N];

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

void dfs(int v){
    mark[v] = true;
    for(int u: adj[v]){
        if(!mark[u]) dfs(u);
    }
}

bool check(ld r){
    for(int i = 1; i <= n; i++) adj[i].clear();

    for(int i = 1; i <= n; i++){
        for(int j = i+1; j <= n; j++){
            if(dist(i, j) <= r * r * 4){
                adj[i].pb(j); adj[j].pb(i);
            }
        }
    }

    fill(mark, mark + N, 0);

    int cnt = 0;
    for(int i = 1; i <= n; i++){
        if(!mark[i]){
            dfs(i); cnt++;
        }
    }

    return cnt == 1;
}

int main(){
    fast_io;

    cin >> n;

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

    if(n == 1) kill(0);

    ld l = 0, r = 2e9;
    for(int i = 0; i < 100; i++){
        ld mid = (l+r)/2;
        if(check(mid)) r = mid;
        else l = mid;
    }

    set_dec(8);
    cout << r;

}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 38 ms 1372 KB Output is correct
7 Correct 38 ms 1368 KB Output is correct
8 Correct 87 ms 3572 KB Output is correct
9 Correct 117 ms 4444 KB Output is correct
10 Correct 101 ms 4444 KB Output is correct