Pagini recente » Cod sursa (job #2711658) | Cod sursa (job #1153909) | Cod sursa (job #1303142) | Cod sursa (job #1190881) | Cod sursa (job #2490134)
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#include <map>
#define pb push_back
#define ll long long
using namespace std;
vector <pair<ll,ll> > v;
ll dist(pair <ll,ll> a,pair<ll,ll> b)
{
int p1x=a.first;
int p1y=a.second;
int p2x=b.first;
int p2y=b.second;
return /*sqrt*/((double)((long long)((long long)p1x-p2x)*(p1x-p2x)+(long long)((long long)p1y-p2y)*(p1y-p2y)));
}
bool compare(pair <int,int> a,pair <int,int> b)
{
if(a.first!=b.first)
{
return (a.first<b.first);
}
else
{
return (a.second<b.second);
}
}
ll divideEtImpera(int st,int dr)
{
int mij,minL,minR;
ll d;
if(dr-st==3)
{
ll first,nd,rd;
first=dist(v[0],v[1]);
nd=min(first,dist(v[1],v[2]));
rd=min(nd,dist(v[0],v[2]));
d=rd;
return d;
}
if(dr-st==2 || dr-st==1)
{
d=dist(v[0],v[1]);
}
int i,j;
mij=st+(dr-st)/2;
d=min(divideEtImpera(st,mij),divideEtImpera(mij,dr));
vector <pair<ll,ll> > new_v;
for(i=st;i<dr;i++)
{
new_v.pb({v[i].first,v[i].second});
}
sort(new_v.begin(),new_v.end());
for(i=0;i<new_v.size();i++)
{
for(j=i+1;j<new_v.size();j++)
{
if(j<i+8)
{
ll new_d;
new_d=dist(new_v[i],new_v[j]);
if(new_d<d)
{
d=new_d;
}
}
}
}
}
int main()
{
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n,i,j,a,b;
double f;
double min=999999999;
fin>>n;
for(i=1;i<=n;i++)
{
fin>>a>>b;
v.pb({a,b});
}
int dist_best=1e9;
sort(v.begin(),v.end());
dist_best=divideEtImpera(1,n);
fout<<sqrt(dist_best);
fin.close();
fout.close();
return 0;
}