Pagini recente » Cod sursa (job #2773864) | Cod sursa (job #317549) | Cod sursa (job #1776027) | Cod sursa (job #1657892) | Cod sursa (job #2669648)
/*#include<iostream>
#include<fstream>
#include<queue>
#include<vector>
#define N (int)1e5+5
using namespace std;
int n,m,p,k,ind[N],sub[N],indeg[N];
int match[N];
vector<int> G[N];
void read()
{
//ifstream fin("marvel.in");
freopen("marvel.in","r",stdin);
scanf("%d%d%d%d",&n,&m,&p,&k);
for(int i=1;i<=n;++i)
scanf("%d",&ind[i]);
for(int i=1;i<=k;++i)
scanf("%d",&sub[i]);
for(int i=0;i<m;++i){
int x,y;
scanf("%d%d",&x,&y);
G[x].push_back(y);
++indeg[y];
}
//fin.close();
}
void bfs()
{
queue<int> q;
q.push(1);
while(!q.empty())
{
int curr = q.front();
q.pop();
int pos = match[curr];
if(sub[pos+1]==ind[curr])
++match[curr];
for(auto& i:G[curr])
{
match[i]=max(match[i],match[curr]);
--indeg[i];
if(!indeg[i])
q.push(i);
}
}
}
void solve()
{
freopen("marvel.out","w",stdout);
vector<int> ans;
for(int i=1;i<=n;++i)
if(match[i]==k)
ans.emplace_back(i);
cout<<ans.size()<<'\n';
for(auto& i:ans)
cout<<i<<' ';
}
int main()
{
read();
bfs();
solve();
return 0;
}*/
//cmap
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define mp make_pair
using namespace std;
ll solve(const int& n,vector<pii>& pct)
{
sort(pct.begin(),pct.end());
set<pii> s;
//cout<<pct[0].first<<' '<<pct[0].second<<'\n';
int j=0;
ll dc=1e18;
for(int i=0;i<n;++i)
{
int d = ceil(sqrt(dc));
while(pct[i].first-pct[j].first>=d){
pii ds=mp(pct[j].second,pct[j].first);
s.erase(ds);
++j;
}
set<pii>::iterator jos = s.lower_bound(mp(pct[i].second-d,pct[i].first));
set<pii>::iterator sus = s.lower_bound(mp(pct[i].second+d,pct[i].first));
for(auto& it=jos;it!=sus;++it)
{
int dx=pct[i].first-it->second;
int dy=pct[i].second-it->first;
dc=min(dc,1ll*dx*dx+1ll*dy*dy);
}
s.insert(mp(pct[i].second,pct[i].first));
}
return dc;
}
int main()
{
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n;
fin>>n;
vector<pii> p(n);
for(int i=0;i<n;++i)
fin>>p[i].first>>p[i].second;
fout<<fixed<<setprecision(6)<<sqrt(solve(n,p));
fin.close();
fout.close();
}