# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
807020 | tlnk07 | Odašiljači (COCI20_odasiljaci) | C++17 | 340 ms | 340 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>
using namespace std;
#define int long long
long long n, p[1001], limit = 100;
double l = 0, r = 1e9;
pair<int, int> a[1001];
int findparent(int x)
{
if(x == p[x]) return x;
else return p[x] = findparent(p[x]);
}
bool check(double x)
{
for(int i = 1; i <= n; ++i) p[i] = i;
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= n; ++j)
{
double temp = (a[i].first - a[j].first) * (a[i].first - a[j].first) + (a[i].second - a[j].second) * (a[i].second - a[j].second);
if(sqrt(temp) < x * 2)
{
long long a = findparent(i), b = findparent(j);
p[a] = p[b];
}
}
}
p[1] = findparent(1);
for(int i = 2; i <= n; ++i) if(findparent(i) != p[1]) return 0;
return 1;
}
signed main()
{
cin >> n;
for(int i = 1; i <= n; ++i) cin >> a[i].first >> a[i].second;
while(l < r && limit--)
{
double mid = (l + r) / 2;
if(!check(mid)) l = mid;
else r = mid;
}
cout << fixed << setprecision(7) << l;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |