oj.uz

Submission #904176

# Submission time Handle Problem Language Result Execution time Memory
904176 2024-01-11T21:04:23 Z vjudge1 Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 126 ms 456 KB 
#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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 44 ms 348 KB Output is correct
7 Correct 45 ms 344 KB Output is correct
8 Correct 95 ms 348 KB Output is correct
9 Correct 126 ms 344 KB Output is correct
10 Correct 100 ms 456 KB Output is correct