Submission #934732

#TimeUsernameProblemLanguageResultExecution timeMemory
934732ASGA_RedSeaOdašiljači (COCI20_odasiljaci)C++17
70 / 70
153 ms532 KiB

/**

                                    * بسم الله الرحمن الرحيم *

                ﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿

*/

/// author : "ASGA_RedSea"

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

#ifdef ONLINE_JUDGE
    #define endl '\n'
#endif

using ll = long long;
using ld = long double;
using ull = unsigned long long;

const ll mod = 1000000007;

ld m,e = 1e-7;
int n;

vector <pair <ld,ld>> a;
vector <int> v;

void calc(int i){
    v[i] = 1;
    for(int j = 0;j < n;j++){
        if(v[j])continue;
        if(sqrt(pow(abs(a[i].first - a[j].first),2.0) + (pow(abs(a[i].second - a[j].second),2.0))) - (m * 2.0) <= e)calc(j);
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cout << fixed << setprecision(6);
    ///cout.tie(0);

    ///freopen("test.in", "r", stdin);
    ///freopen("test.out", "w", stdout);

    cin >> n;
    a.resize(n);
    for(auto& i : a)cin >> i.first >> i.second;

    ld l = 0.00000000,r = 2000000000.00000000;
    while(r - l >= e){
        m = (l + r) / 2;
        int f = 1;

        v = vector <int> (n,0);
        calc(0);
        for(int i = 1;i < n && f;i++){
            if(v[i] == 0)f = 0;
        }

        if(f)r = m - e;
        else l = m + e;
    }

    cout << l << endl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...