Submission #922341

#	Time	Username	Problem	Language	Result	Execution time	Memory
922341		Shayan86	Odašiljači (COCI20_odasiljaci)	C++14	70 / 70	117 ms	4444 KiB

odasiljaci

#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 / 70