Submission #904158

#	Time	Username	Problem	Language	Result	Execution time	Memory
904158		vjudge1	Odašiljači (COCI20_odasiljaci)	C++17	70 / 70	125 ms	452 KiB

odasiljaci

#include <bits/stdc++.h>
using namespace std;
#define repf(i,k,n) for(int i=k; i<n; i++)
#define rep(i,n) for(int i=0; i<n; i++)

typedef vector<int> vi;

struct DSU{
	vi p,size;
	DSU(int n){
		p.resize(n);
		rep(i,n) p[i]=i;
		size.assign(n,1);
	};
	int find(int x){
		return (x==p[x] ? x : p[x]=find(p[x]));
	}
	void join(int a, int b){
		int x=find(a), y=find(b);
		if(x==y) return;
		if(size[x]<size[y]) swap(x,y);
		p[x]=y;
		size[y]+=size[x];
	}
	bool isSame(int a, int b){
		return find(a)==find(b);
	}
	int sz(int x){
		return size[find(x)];
	}
};

bool check(vi &x, vi &y, double r){
	int n=x.size();
	DSU dsu(n);
	rep(i,n){
		rep(j,n){
			double a=(x[i]-x[j]),
					  b=(y[i]-y[j]);
			if(a*a+b*b<=4*r*r) dsu.join(i,j); 
		}
	}
	return dsu.sz(0)==n;
}

int main(){ 
	ios::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	vi x(n), y(n);
	rep(i,n) cin>>x[i]>>y[i];

	cout << setprecision(7);
	double l=0, r=1e9, e=1e-7;
	while(l+e<r){
		double m=(l+r)/2;
		//cerr << m << '\n';
		if(check(x,y,m))
			r=m;
		else
			l=m+e;
	}
	cout << l << '\n';
	return 0;
}

• Subtask 1: 70 / 70