Submission #904232

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
904232	2024-01-12T00:57:44 Z	vjudge1	Odašiljači (COCI20_odasiljaci)	C++17	70 / 70	124 ms	484 KB

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.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	356 KB	Output is correct
2	Correct	0 ms	356 KB	Output is correct
3	Correct	1 ms	356 KB	Output is correct
4	Correct	1 ms	356 KB	Output is correct
5	Correct	1 ms	448 KB	Output is correct
6	Correct	45 ms	360 KB	Output is correct
7	Correct	46 ms	360 KB	Output is correct
8	Correct	93 ms	472 KB	Output is correct
9	Correct	124 ms	480 KB	Output is correct
10	Correct	97 ms	484 KB	Output is correct