oj.uz

Submission #934732

# Submission time Handle Problem Language Result Execution time Memory
934732 2024-02-27T21:57:54 Z ASGA_RedSea Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 153 ms 532 KB 
/**

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

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

*/

/// 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;
}

Subtask #1
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 16 ms 348 KB Output is correct
7 Correct 25 ms 348 KB Output is correct
8 Correct 67 ms 348 KB Output is correct
9 Correct 135 ms 348 KB Output is correct
10 Correct 153 ms 532 KB Output is correct