Submission #356365

#	Time	Username	Problem	Language	Result	Execution time	Memory
356365		fbosnjak	Odašiljači (COCI20_odasiljaci)	C++14	70 / 70	80 ms	8792 KiB

odasiljaci

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

const int maxn = 1000;
int par[maxn];

double Dist(double a1, double b1, double a2, double b2) {
    return sqrt((a1 - a2)*(a1 - a2) + (b1 - b2)*(b1 - b2));
}
int Find(int x) {
    return (x == par[x]) ? x : par[x] = Find(par[x]);
}
bool Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x != y) {par[x] = y; return true;}
    return false;
}

int main() 
{
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) par[i] = i;
    double x[N], y[N];
    vector <pair <double, pair <int, int> > > v;
    for (int i = 0; i < N; i++) {
        cin >> x[i] >> y[i];
        for (int j = 0; j < i; j++) {
            v.push_back(make_pair(Dist(x[i], y[i], x[j], y[j]), make_pair(i, j)));
        }
    }
    sort(v.begin(), v.end());
    double sol = 0.0;
    for (int i = 0; i < v.size(); i++) {
        int a = v[i].second.first;
        int b = v[i].second.second;

        if (Union(a, b)) sol = v[i].first / 2;
    }

    printf("%.9f\n", sol);
}

Compilation message (stderr)

odasiljaci.cpp: In function 'int main()':
odasiljaci.cpp:35:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<double, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~

• Subtask 1: 70 / 70