Pagini recente » Cod sursa (job #3293615) | Rating Papa Victor (papinub) | Cod sursa (job #3294288) | Rezultatele filtrării | Cod sursa (job #3294289)
#include <bits/stdc++.h>
#define VMAX 100005
#define INF 200000000000000000
using namespace std;
ifstream fin ("cmap.in");
ofstream fout ("cmap.out");
struct pct{
long long int i,j;
};
vector<pct> puncte;
long long int dist_min=INF;
bool comp(pct a, pct b)
{
return a.j<b.j || a.j==b.j && a.i<b.i;
}
bool comp2(pct a, pct b)
{
return a.i<b.i || a.i==b.i && a.j<b.j;
}
long long int dist(pct a, pct b)
{
return (a.i-b.i)*(a.i-b.i)+(a.j-b.j)*(a.j-b.j);
}
void divide_et_imp(int st, int dr)
{
int i,j;
if(dr-st<=2)
{
for(i=st;i<=dr;i++)
{
for(j=i+1;j<=dr;j++)
dist_min=min(dist_min,dist(puncte[i],puncte[j]));
}
if(dr-st==1) // 2 numere
{
if(!comp2(puncte[st],puncte[dr]))
swap(puncte[st],puncte[dr]);
}
else if(dr-st==2)
{
if(!comp2(puncte[st],puncte[dr-1]))
swap(puncte[st],puncte[dr-1]);
if(!comp2(puncte[dr-1],puncte[dr]))
swap(puncte[dr-1],puncte[dr]);
if(!comp2(puncte[st],puncte[dr-1]))
swap(puncte[st],puncte[dr-1]);
}
return;
}
int mij = (st+dr)/2;
divide_et_imp(st,mij);
divide_et_imp(mij+1,dr);
vector<pct> candidati_merge;
for(i=st;i<=dr;i++)
if((puncte[mij].j-puncte[i].j)*(puncte[mij].j-puncte[i].j)<=dist_min)
candidati_merge.push_back(puncte[i]);
sort(candidati_merge.begin(),candidati_merge.end(),comp2);
for(i=0;i<candidati_merge.size();i++)
{
for(j=1;j<=8 && i+j<candidati_merge.size();j++)
dist_min=min(dist_min,dist(candidati_merge[i],candidati_merge[i+j]));
}
}
int main()
{
int n,m,i,j,k,t,q,nr,minim,maxim,suma;
pct model;
fin>>n;
for(i=0;i<n;i++)
{
fin>>model.j>>model.i;
puncte.push_back(model);
}
sort(puncte.begin(),puncte.end(),comp);
divide_et_imp(0,n-1);
fout<<fixed<<setprecision(11)<<sqrtl(dist_min)<<'\n';
return 0;
}