Submission #332189

#TimeUsernameProblemLanguageResultExecution timeMemory
332189DanerZeinOdašiljači (COCI20_odasiljaci)C++14
70 / 70
154 ms8804 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> ii; typedef pair<double,ii> iii; const ll MAX=1e9; int ns; double raiz(ll x){ double l=0,r=MAX; for(int i=0;i<=40;i++){ double mid=(l+r)/2; if(mid*mid>=x)r=mid; else l=mid; } return r; } int pa[1010]; void init(int n){ for(int i=0;i<n;i++) pa[i]=i; ns=n; } int findset(int i){ if(pa[i]==i) return pa[i]; return pa[i]=findset(pa[i]); } bool issameset(int i,int j){ return findset(i)==findset(j); } void unionset(int i,int j){ if(!issameset(i,j)){ int x=findset(i),y=findset(j); ns--; pa[x]=y;; } } vector<ii> x; bool check(double r,int n){ init(n); //cout<<r<<endl; for(int i=0;i<n-1;i++){ for(int j=i+1;j<n;j++){ if(!issameset(i,j)){ double a=abs(x[i].first-x[j].first); double b=abs(x[i].second-x[j].second); double dist=raiz((a*a)+(b*b)); dist/=2; // cout<<i<<" "<<j<<" "<<dist<<" "<<r<<" "<<ns<<endl; if(dist<=r) unionset(i,j); } } } if(ns==1) return true; return false; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin>>n; for(int i=0;i<n;i++){ int a,b; cin>>a>>b; x.push_back(ii(a,b)); } priority_queue<iii,vector<iii>,greater<iii> > pq; for(int i=0;i<n-1;i++){ for(int j=i+1;j<n;j++){ double a=abs(x[i].first-x[j].first); double b=abs(x[i].second-x[j].second); double dist=sqrt((a*a)+(b*b)); dist/=2; pq.push(iii(dist,ii(i,j))); } } double mi=-1; init(n); while(!pq.empty()){ int u,v; double dist; u=pq.top().second.first; v=pq.top().second.second; dist=pq.top().first; pq.pop(); if(!issameset(u,v)){ mi=max(mi,dist); } unionset(u,v); }printf("%.7f\n",mi); }
#Verdict Execution timeMemoryGrader output
Fetching results...