#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> padre, sz; // padre y tamao, hay que inicializar el tamaño
int lider(int nodo){
if(nodo == padre[nodo]) return nodo;
return padre[nodo] = lider(padre[nodo]);
}
bool IsSameSet(int a, int b){ //revisa si a y b estanen una misma componente
return lider(a) == lider(b);
}
void Union(int a, int b){ //une a con b
a=lider(a);
b=lider(b);
if(a==b) return;
if(sz[a] < sz[b]) swap(a,b);
sz[a] += sz[b];
padre[b] = a;
}
ll pit(ll k,ll t, ll ki,ll ti){
ll kii = (k-ki)*(k-ki);
ll tii = (t-ti)*(t-ti);
return kii + tii;
}
int main() {
int n;
const int x = 0;
const int y = 1;
cin>> n;
sz.assign(n,1);
padre.resize(n);
vector<vector<long long>>v(n, vector<long long>(2));
for(int i = 0; i<n;i++){
cin>> v[i][x] >> v[i][y];
padre[i] = i;
}
vector<vector<ll>> nar(n*n, vector<ll>(3));
int ii = 0;
long double maxkrusk = 0;
for (int i = 0;i<n;i++){
for (int j = 0;j<n;j++){
nar[ii][0] = pit(v[i][x],v[i][y], v[j][x], v[j][y] );
nar[ii][1] = i;
nar[ii][2] = j;
//cout<< ar[ii]<<endl;
//cerr << nar[ii][0] << '\n';
ii++;
}
}
//sort(ar.begin(), ar.end());
sort(nar.begin(), nar.end()); // x i j
for(int i = 0; i<n*n;i++){
if (IsSameSet(nar[i][1], nar[i][2]))continue;
Union(nar[i][1], nar[i][2]);
maxkrusk = nar[i][0];
}
maxkrusk = sqrt(maxkrusk);
maxkrusk /= 2;
cout << maxkrusk << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 5 |
Correct |
2 ms |
856 KB |
Output is correct |
| 6 |
Correct |
81 ms |
14168 KB |
Output is correct |
| 7 |
Correct |
94 ms |
14172 KB |
Output is correct |
| 8 |
Incorrect |
271 ms |
31068 KB |
Output isn't correct |
| 9 |
Correct |
534 ms |
55120 KB |
Output is correct |
| 10 |
Incorrect |
542 ms |
55436 KB |
Output isn't correct |
