Submission #1152291

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152291		yhkhoo	Odašiljači (COCI20_odasiljaci)	C++20	70 / 70	456 ms	460 KiB

odasiljaci

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
#define fi first
#define se second

const int MAXN = 1000;
int p[MAXN];
pii a[MAXN];

int par(int x){
    if(p[x] == x) return x;
    return (p[x] = par(p[x]));
}

bool un(int u, int v){
    u = par(u); v = par(v);
    if(u == v) return 0;
    p[u] = v;
    return 1;
}

int main(){
    cin.tie(0); ios_base::sync_with_stdio(0);
    int n;
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        scanf("%d", &a[i].fi);
        scanf("%d", &a[i].se);
    }
    long double l=0, r=1e9, m;
    while(r-l > 0.0000001){
        for(int i=0; i<n; i++){
            p[i] = i;
        }
        m = (r+l)/2;
        for(int i=0; i<n; i++){
            for(int j=i; j<n; j++){
                if(hypot(a[i].fi - a[j].fi, a[i].se - a[j].se) <= m){
                    un(i, j);
                }
            }
        }
        bool yes=1;
        for(int i=0; i<n-1; i++){
            if(par(i) != par(i+1)){
                yes = 0;
                break;
            }
        }
        if(yes){
            r = m;
        }
        else{
            l = m;
        }
    }
    auto ret = (l+r)/4;
    printf("%.7Lf", ret);
    return 0;
}

Compilation message (stderr)

odasiljaci.cpp: In function 'int main()':
odasiljaci.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
odasiljaci.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         scanf("%d", &a[i].fi);
      |         ~~~~~^~~~~~~~~~~~~~~~
odasiljaci.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         scanf("%d", &a[i].se);
      |         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 70 / 70