# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
935018 | mostafa133 | Odašiljači (COCI20_odasiljaci) | C++14 | 105 ms | 728 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |