Submission #1318141

#TimeUsernameProblemLanguageResultExecution timeMemory
1318141asimOdašiljači (COCI20_odasiljaci)C++20
0 / 70
69 ms1092 KiB
// created : 2026/02/01 18:28:38
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define all(v) v.begin(), v.end()
#define double long double

void solve()
{
    int n;
    cin >> n;
    vector<pair<double, double>> vt;
    for (int i = 0; i < n; i++)
    {
        double x, y;
        cin >> x >> y;
        vt.pb({x, y});
    }
    double EPS = 0.0000000001;
    double l = 0.0, r = 1000000000000000000.0;
    double best = 4e18;
    while (r - l > EPS)
    {
        double m = (l + r) / 2;
        multiset<pair<double, double>> st;
        for(int i = 0; i < n; i++) {
            double x = vt[i].first, y = vt[i].second;
            st.insert({x + m, y}), st.insert({x, y + m}), st.insert({x + m, y + m}), st.insert({x - m, y}), st.insert({x, y - m}), st.insert({x - m, y - m}), st.insert({x - m, y + m}), st.insert({x + m, y - m});
        }
        bool ok = true;
        for(int i = 0; i < n; i++) {
            double x = vt[i].first, y = vt[i].second;
            st.erase(st.find({x + m, y})), st.erase(st.find({x, y + m})), st.erase(st.find({x + m, y + m})), st.erase(st.find({x - m, y})), st.erase(st.find({x, y - m})), st.erase(st.find({x - m, y - m})), st.erase(st.find({x + m, y - m})), st.erase(st.find({x - m, y + m}));
            if(st.find({x + m, y}) == st.end() and st.find({x, y + m}) == st.end() and st.find({x + m, y + m}) == st.end() and st.find({x - m, y}) == st.end() and st.find({x - m, y - m}) == st.end() and st.find({x, y - m}) == st.end() and st.find({x + m, y - m}) == st.end() and st.find({x - m, y + m}) == st.end()) {
                ok = false;
                break;
            }
            st.insert({x + m, y}), st.insert({x, y + m}), st.insert({x + m, y + m}), st.insert({x - m, y}), st.insert({x, y - m}), st.insert({x - m, y - m}), st.insert({x - m, y + m}), st.insert({x + m, y - m});
        }
        if(ok) {
            r = m;
            best = min(best, m);
        }
        else {
            l = m;
        }
    }
    cout << fixed << setprecision(6);
    cout << best << '\n';
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--)
    {
        solve();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...