Submission #356522

#	Time	Username	Problem	Language	Result	Execution time	Memory
356522		dogav	Odašiljači (COCI20_odasiljaci)	C++14	70 / 70	659 ms	47420 KiB

odasiljaci

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1001;

struct edge {
	double x;
	double y;
	int id;
	
	edge(int id, int x, int y) {
		this->id = id;
		this->x = x;
		this->y = y;
	}
	
	bool operator<(const edge a) const {
		return true;
	}
	
	string print() {
		return to_string(x) + " " + to_string(y);
	}
};

double dist(edge x, edge y) {
	return sqrt((x.x - y.x)*(x.x - y.x) + (x.y - y.y)*(x.y - y.y));
}

int par[MAXN];

int Find(int x) {
	if (x == par[x]) return par[x];
	return 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;
	
	vector<edge> edgevi;
	set< pair <double, pair< edge, edge > > >s;
	
	for (int i = 0; i < n; i++) {
		par[i] = i;
		int x,y;
		cin >> x >> y;
		edgevi.push_back(edge(i,x,y));
		for (int j = 0; j < i; j++) {
			edge e = edge(i,x,y);
			double udaljenost = dist(e, edgevi[j]);
			s.insert({udaljenost, {e, edgevi[j]}});
		}
	}
	
	double output = 0;
	for (auto it = s.begin(); it != s.end(); it++) {
		pair<double, pair<edge, edge>> p = (*it);
		if (Union(p.second.first.id, p.second.second.id)) {
			output = p.first / 2;
		}
	}
	printf("%.07f", output);
	
}

• Subtask 1: 70 / 70