Pagini recente » Cod sursa (job #2070608) | Cod sursa (job #880049) | Cod sursa (job #2073266)
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
struct Punct
{
int x = 0;
int y = 0;
};
double calculDist(Punct a, Punct b)
{
double x = a.x - b.x;
double y = a.y - b.y;
double d;
d = pow(x,2) + pow(y,2);
return d;
}
bool cmpY(const Punct& a, const Punct &b)
{
return a.y < b.y;
}
bool cmpX(const Punct & a, const Punct &b)
{
return a.x < b.x;
}
double DI(int st, int dr, vector<Punct> &pY,vector<Punct> &P)
{
if(dr - st == 1)
return 2147483647;
if(dr - st == 2)
{
if(pY[st].y > pY[st+1].y)
swap(pY[st], pY[st+1]);
return calculDist(P[0],P[1]);
}
int m = (st + dr)/2,i,j;
double distSt = DI(st,m,pY,P);
double distDr = DI(m,dr,pY,P);
double distRecursie = min(distSt, distDr);
vector<Punct> verif(dr - st);
merge(pY.begin() + st, pY.begin() + m, pY.begin() + m, pY.begin() + dr, verif.begin(), cmpY);
copy(verif.begin(), verif.begin() + (dr - st), pY.begin() + st);
vector<Punct> z;
for(i = st; i < dr; i++)
if(abs(pY[i].x - P[m].x) <= distRecursie)
z.push_back(pY[i]);
///sort(verif.begin(),verif.end(),cmp);
double distFinala = distRecursie;
for(int i = 0; i < z.size(); i++)
for(int j = i+1;j< 7 && z[j].y - z[i].y <= distRecursie; j++)
{
double dC = calculDist(z[i],z[j]);
if(dC < distFinala)
distFinala = dC;
}
return distFinala;
}
int main()
{
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int x,y,i;
int n;
fin>>n;
vector<Punct>P(n);
for(i = 0; i < n; i++)
{
fin>>P[i].x;
fin>>P[i].y;
}
sort(P.begin(),P.end(),cmpX);
vector<Punct> pY = P;
fout<<fixed<<setprecision(6)<<sqrt(DI(0,P.size(),pY,P))<<"\n";
fin.close();
fout.close();
return 0;
}