#include <bits/stdc++.h>
using namespace std;
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")
#define ll long long
#define int128 __int128_t
#define pii pair<int, int>
#define int long long
#define pb push_back
#define F first
#define S second
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).begin(), (v).end()
#define MOD 1000000007
#define INF (ll)1e18
#define RINF (ll) - 1e18
void cinv(vector<int> &a, int n){for (int i = 0; i < n; i++){cin >> a[i];}}
void coutv(vector<int> &a, int n){for (int i = 0; i < n; i++){cout << a[i] << " ";}}
bool bfs(int s,int n,vector<int>a[]){
queue<int>q;
vector<int>color(n+1,0);
q.push(s);
color[s] = 1;
while(q.size()!=0){
int g = q.front();
for(int i:a[g]){
if(color[i]==0){
q.push(i);
color[i] = 1;
}
}
q.pop();
}
for(int i = 1;i<=n;i++){
if(color[i]!=1){
return false;
}
}
return true;
}
void solve()
{
int n;
cin>>n;
vector<pair<int,int>>q11;
for(int i = 0;i<n;i++){
int x,y;
cin>>x>>y;
q11.push_back({x,y});
}
sort(q11.begin(),q11.end());
long double l = 0,r = 1e18;
long double ans = 0;
while((r-l)>(long double)1/1e7){
long double mid = (l+r)/(long double)2;
vector<long double>dx = {mid, -mid, 0, 0};
vector<long double>dy = {0, 0, mid, -mid};
set<int>q1;
for(int i = 0;i<n;i++){
q1.insert(i);
}
vector<int>sss[n+1];
for(int i = 0;i<n-1;i++){
int qqqq = 0;
for(int j = 0;j<n;j++){
bool g = false;
long double q = q11[i].F, y = q11[i].S;
long double e = q11[j].F, r = q11[j].S;
long double g11 = (q-e)*(q-e)+(y-r)*(y-r);
long double q11 = 4*mid*mid;
if(g11<=q11){
sss[i+1].push_back(j+1);
sss[j+1].push_back(i+1);
}
// cout<<i<<" "<<j<<" "<<g11<<" "<<q11<<endl;
}
}
bool g111 = bfs(1,n,sss);
if(g111){
ans = mid;
r = mid;
}
else{
l = mid;
}
// cout<<setprecision(7)<<fixed<<ans<<" "<<l<<" "<<r<<" "<<g111<<endl;
// cout<<endl;
}
cout<<setprecision(7)<<fixed<<min(l,r)<<endl;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |