#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 long long mx=1005;
long long sz[1005],p[1005];
long long par(long long x){
if(p[x]==x)return x;
return p[x]=par(p[x]);
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
long long n;cin >> n;
vector <pair <long long,long long > > a;
rep(i,n){
long long x,y;cin >> x >> y;
a.pb(mp(x,y));
}
long double l=0;long double r=2e9;
while(r>l+0.000001){
long double mid=(l+r)/2;
bool ok=false;
rep(i,mx)sz[i]=1;
rep(i,mx)p[i]=i;
for(long long i=0;i<n;++i){
for(long long j=0;j<n;++j){
long 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+0.000001)continue;//mid e arti 0.0000001 ekle
par(i);par(j);
if(p[i]==p[j])continue;
// prlong longf("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(long long i=0;i<n;++i){
if(sz[i]==n)ok=true;
//prlong longf("i:%d sz[i]:%d ok:%d\n",i,sz[i],ok);
}
if(ok)r=mid;
else l=mid+0.000001;
//prlong longf("%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;
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
3 ms |
204 KB |
Output is correct |
| 4 |
Correct |
5 ms |
204 KB |
Output is correct |
| 5 |
Correct |
7 ms |
332 KB |
Output is correct |
| 6 |
Correct |
166 ms |
332 KB |
Output is correct |
| 7 |
Correct |
168 ms |
332 KB |
Output is correct |
| 8 |
Correct |
359 ms |
344 KB |
Output is correct |
| 9 |
Correct |
553 ms |
344 KB |
Output is correct |
| 10 |
Correct |
492 ms |
452 KB |
Output is correct |
