# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
806997 | tlnk07 | Odašiljači (COCI20_odasiljaci) | C++17 | 402 ms | 308 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;
long long n, p[1001], limit = 80;
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 = i + 1; j <= n; ++j)
{
double temp = (abs(a[i].first - a[j].first)) * (abs(a[i].first - a[j].first)) + (abs(a[i].second - a[j].second)) * (abs(a[i].second - a[j].second));
temp *= 1.0;
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;
}
int 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... |