#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
typedef long double ld;
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(x) x.begin(), x.end()
#define fast ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
void dfs(ll cur, vector<bool> &vis, vector<pair<ll, ll>> &v, ld md)
{
if (vis[cur])
{
return;
}
vis[cur] = 1;
for (int i = 0; i < vis.size(); i++)
{
if (vis[i])
continue;
ll x = abs(v[i].first - v[cur].first), y = abs(v[i].second - v[cur].second);
ll dis = x * x + y * y;
if (sqrt(dis) > md)
{
// cout << md << ' ' << md * md;
continue;
}
dfs(i, vis, v, md);
}
// if ((v[cur].second) > md * md)
{
// cout << md << ' ' << md * md;
// return;
}
}
int main()
{
fast;
// freopen("pails.in", "r", stdin);
// freopen("pails.out", "w", stdout);
ll n;
cin >> n;
vector<pair<ll, ll>> v(n);
for (int i = 0; i < n; i++)
{
cin >> v[i].first >> v[i].second;
}
// ll mx = 0;
vector<pair<ll, ll>> close(n);
for (int i = 0; i < n; i++)
{
ll mn = LLONG_MAX, mnin = 0;
for (int j = 0; j < n; j++)
{
if (j == i)
{
continue;
}
ll x = abs(v[i].first - v[j].first), y = abs(v[i].second - v[j].second);
ll dis = x * x + y * y;
if (dis < mn)
{
mn = dis, mnin = j;
}
}
close[i] = {mnin, mn};
}
// for (int i = 0; i < n; i++)
{
// cout << i << ": " << close[i].first << ' ' << close[i].second << '\n';
}
ld l = 0, r = 1e9;
vector<bool> vis;
while (l <= r)
{
ld md = (l + r) / 2;
vis = vector<bool>(n, 0);
dfs(0, vis, v, md);
// for (int i = 0; i < n; i++)
{
// cout << vis[i];
}
// if (md < 2)
{
// for (int i = 0; i < n; i++)
{
// cout << md;
}
// cout << '\n';
}
// cout << '\n';
if (find(all(vis), 0) == vis.end())
{
// cout << 1;
r = md - 1e-7;
}
else
{
l = md + 1e-7;
}
}
// cout << '\n';
cout << fixed << setprecision(10) << l / 2;
return 0;
}
Compilation message
odasiljaci.cpp: In function 'void dfs(ll, std::vector<bool>&, std::vector<std::pair<long long int, long long int> >&, ld)':
odasiljaci.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bool>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for (int i = 0; i < vis.size(); i++)
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
14 ms |
348 KB |
Output is correct |
| 7 |
Correct |
20 ms |
344 KB |
Output is correct |
| 8 |
Correct |
50 ms |
508 KB |
Output is correct |
| 9 |
Correct |
97 ms |
388 KB |
Output is correct |
| 10 |
Correct |
103 ms |
348 KB |
Output is correct |
