#include "bits/stdc++.h"
#define endl '\n'
constexpr int maxn = 1005;
constexpr int inf = 1e9;
constexpr int mod = 1e9+7;
using namespace std;
using lint = long long;
using pdd = pair<double, double>;
#define x first
#define y second
double eps = 0.0000001;
int n;
pdd pt[maxn];
vector<int> adj[maxn];
bool vis[maxn];
double r;
void dfs(int u) {
vis[u] = true;
for(int v : adj[u]) {
if(vis[v])
continue;
dfs(v);
}
}
bool inter(pdd& a, pdd& b) {
double dist = sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));
return dist < 2 * r;
}
bool check() {
for(int i = 0; i < n; i++) {
vis[i] = false;
adj[i].clear();
}
for(int i = 0; i < n; i++)
for(int j = 1; j < n; j++)
if(inter(pt[i], pt[j])) {
adj[i].push_back(j);
adj[j].push_back(i);
}
dfs(0);
for(int i = 0; i < n; i++)
if(!vis[i])
return false;
return true;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i = 0; i < n; i++)
cin >> pt[i].x >> pt[i].y;
double lft = 0, rgt = 1e9;
while(abs(rgt - lft) > eps) {
r = (lft + rgt) / 2;
if(check())
rgt = r;
else
lft = r;
}
cout << setprecision(9) << fixed << r << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
460 KB |
Output is correct |
| 6 |
Correct |
118 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
115 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
252 ms |
6456 KB |
Output is correct |
| 9 |
Correct |
309 ms |
8520 KB |
Output is correct |
| 10 |
Correct |
212 ms |
8968 KB |
Output is correct |
