#include <bits/stdc++.h>
using namespace std;
#define zaman cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds "
#define rep(i,n) for(long long (i)=0;(i)<(n);++(i))
#define ref(i,a,b) for (long long (i)=(a); (i)<=(b); ++(i))
#define endl '\n'
#define ll long long
#define pb push_back
#define pii pair<ll,ll>
#define mp make_pair
const int mx=1005;
int sz[1005],p[1005];
int par(int x){
if(p[x]==x)return x;
return p[x]=par(p[x]);
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n;cin >> n;
vector <pair <int,int > > a;
rep(i,n){
int x,y;cin >> x >> y;
a.pb(mp(x,y));
}
double l=0;double r=2e9;
while(r>l+0.000001){
double mid=(l+r)/2;
bool ok=false;
rep(i,mx)sz[i]=1;
rep(i,mx)p[i]=i;
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
double dis=(sqrtl((a[i].first-a[j].first)*(a[i].first-a[j].first)+(a[i].second-a[j].second)*(a[i].second-a[j].second)))/2.0;
if(dis>mid)continue;//mid e arti 0.0000001 ekle
par(i);par(j);
if(p[i]==p[j])continue;
// printf("mid:%f dis:%f %d:%d %d:%d\n",mid,dis,i,p[i],j,p[j]);
if(sz[p[i]]>sz[p[j]]){
sz[p[i]]+=sz[p[j]];
sz[p[j]]=0;
p[p[j]]=p[i];
}
else{
sz[p[j]]+=sz[p[i]];
sz[p[i]]=0;
p[p[i]]=p[j];
}
}
}
for(int i=0;i<n;++i){
if(sz[i]==n)ok=true;
//printf("i:%d sz[i]:%d ok:%d\n",i,sz[i],ok);
}
if(ok)r=mid;
else l=mid+0.000001;
//printf("%f %f %d\n",l,r,ok);
}
cout << fixed << setprecision(9) << l << endl;
}
Compilation message
odasiljaci.cpp: In function 'int main()':
odasiljaci.cpp:4:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
4 | #define rep(i,n) for(long long (i)=0;(i)<(n);++(i))
| ^
odasiljaci.cpp:21:2: note: in expansion of macro 'rep'
21 | rep(i,n){
| ^~~
odasiljaci.cpp:4:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
4 | #define rep(i,n) for(long long (i)=0;(i)<(n);++(i))
| ^
odasiljaci.cpp:29:3: note: in expansion of macro 'rep'
29 | rep(i,mx)sz[i]=1;
| ^~~
odasiljaci.cpp:4:32: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
4 | #define rep(i,n) for(long long (i)=0;(i)<(n);++(i))
| ^
odasiljaci.cpp:30:3: note: in expansion of macro 'rep'
30 | rep(i,mx)p[i]=i;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
3 ms |
320 KB |
Output is correct |
| 4 |
Incorrect |
7 ms |
204 KB |
Output isn't correct |
| 5 |
Incorrect |
13 ms |
204 KB |
Output isn't correct |
| 6 |
Correct |
178 ms |
204 KB |
Output is correct |
| 7 |
Correct |
169 ms |
324 KB |
Output is correct |
| 8 |
Correct |
381 ms |
332 KB |
Output is correct |
| 9 |
Execution timed out |
1093 ms |
332 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1098 ms |
332 KB |
Time limit exceeded |
