제출 #1152325

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1152325		jmuzhen	Odašiljači (COCI20_odasiljaci)	C++20	0 / 70	206 ms	824 KiB

odasiljaci

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

typedef long long ll;

#define double long double
using ii = pair<int, int>;
vector<ii> points, pointsy;

inline double dist(ii a, ii b) {
    return sqrt(pow(a.first - b.first, 2.0) + pow(a.second - b.second, 2.0));
}

constexpr double INF = 1e12;
constexpr double EPSILON = pow(10, -7);
const int N=100013;
int g[N];

int find(int x)
{
    if (g[x]==x) return x;
    else return g[x]=find(g[x]);
}
void unite(int x, int y)
{
    x=find(x); y=find(y);
    if (x==y) return;
    g[y]=x;
}

void init() {
    for (int i=0; i<N; i++) g[i]=i;
}

signed main() {
    signed n; cin >> n;

    for (signed i = 0; i < n; i++) {
        int x, y; cin >> x >> y;
        points.push_back({x, y});
    }

    // sort by increasing x
    sort(points.begin(), points.end(), [](const ii&a, const ii&b)
    {
        return a.first<b.first;
    });

    // binary search
    double l = 0, r = INF;
    while (r-l>EPSILON) {
        double mid = (l+r)/2;
        bool ok = true;
        // init ufds
        init();

        for (signed i = 0; i < n; i++) {
            auto p1 = points[i];
            for (signed j = 0; j < n; j++) {
                if (i==j) continue;
                if (find(i) == find(j)) continue;
                auto p2 = points[j];
                double d = dist(p1, p2);
                if (mid*2>=d) {
                    // ok
                    unite(i,j);
                }
                else {
                    ok = false;
                    break;
                }
            }
        }

        if (ok) {
            // can reduce
            r = mid;
        }
        else {
            // must increase
            l = mid;
        }
    }

    // answer is l
    cout << setprecision(7) << l/2 << endl;
}

• Subtask 1: 0 / 70