oj.uz

답안 #474038

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
474038 2021-09-16T16:58:44 Z mychecksedad Odašiljači (COCI20_odasiljaci) C++17
70 / 70
 262 ms 4652 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
const int N = 1010, F = 1e9;


int n;
struct P{
	ll x, y;
	double dist(P a){
		return sqrt((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y));
	}
};
bool check(vector<vector<int>> &g){
	queue<int> q;
	vector<bool> v(1001, 0);
	q.push(0);
	v[0] = 1;
	while(!q.empty()){
		int x = q.front();
		q.pop();
		for(int u: g[x]){
			if(!v[u]){
				v[u] = 1;
				q.push(u);
			}
		}
	}
	bool ok = 1;
	for(int i=0;i<n;i++) ok&=v[i];
	return ok;
}
int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	P arr[N];
	cin >> n;
	for(int i = 0; i < n; i++) cin >> arr[i].x >> arr[i].y;
	double l = 0, r = 2*F, ans = 2*F;
	while(l + (0.000001f) < r){
		double mid = (l+r)/2.0;
		vector<vector<int>> g(N);
		for(int i = 0; i < n; i++){
			for(int j = i+1; j < n; j++){
				double d = arr[i].dist(arr[j]);
				if(d <= mid){
					g[i].pb(j);
					g[j].pb(i);
				}
			}
		}
		if(check(g)){
			ans = min(ans, mid); 
			r = mid;
		}else l = mid;
	}


	cout << fixed <<  setprecision(15);
	cout << l/2.0;

	return 0;
}

Subtask #1
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 4 ms 332 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 106 ms 1388 KB Output is correct
7 Correct 94 ms 1404 KB Output is correct
8 Correct 209 ms 3496 KB Output is correct
9 Correct 262 ms 4652 KB Output is correct
10 Correct 192 ms 4556 KB Output is correct