Pagini recente » Rezultatele filtrării | Notiuni de baza | Cod sursa (job #598098) | Rezultatele filtrării | Cod sursa (job #3294291)
#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;
}
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(st==dr)
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;i+j<candidati_merge.size();j++)
{
if(dist_min<dist(candidati_merge[i],candidati_merge[i+j]))
break;
else
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;
}