#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define endl '\n'
ll calc(ll x ,ll y){
return abs(x - y) * abs(x-y);
}
int n;
vector<bool>vis;
vector<vector<int>>a((1e3) + 5,vector<int>(int(1e3) + 5));
void dfs(int idx,ld mid){
if(vis[idx])
{
return;
}
vis[idx] = 1;
for(int i=0;i<n;i++){
if(i == idx)continue;
if((ld)sqrt(a[idx][i]) > mid)continue;
dfs(i,mid);
}
return;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
vis.resize(n);
vector<pair<ll,ll>>v;
for(int i=0;i<n;i++){
ll x,y;cin >> x >> y;
v.push_back({x,y});
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i == j)continue;
a[i][j] = calc(v[i].first,v[j].first) + calc(v[i].second,v[j].second);
cout << a[i][j] << ' ';
}
cout << endl;
}
ld l = 0.0000000000;
ld r = 2e9;
ld ans =0.00000000000;
for(int i=0;i<1000;i++){
ld mid = (r+l)/2;
vis = vector<bool>(n);
dfs(0,mid);
bool f= false;
for(int i=0;i<n;i++){
if(vis[i] == 0)
{
f = true;
break;
}
}
if(!f){
r = mid;
ans = mid;
}else{
l = mid;
}
}
cout << fixed << setprecision(10) << ans / 2;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
4296 KB |
Output isn't correct |
| 3 |
Incorrect |
12 ms |
4440 KB |
Output isn't correct |
| 4 |
Incorrect |
56 ms |
4440 KB |
Output isn't correct |
| 5 |
Incorrect |
110 ms |
4444 KB |
Output isn't correct |
| 6 |
Incorrect |
893 ms |
5528 KB |
Output isn't correct |
| 7 |
Incorrect |
927 ms |
5468 KB |
Output isn't correct |
| 8 |
Execution timed out |
1031 ms |
7248 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1049 ms |
15440 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1031 ms |
15408 KB |
Time limit exceeded |
