Pagini recente » Cod sursa (job #792417) | Cod sursa (job #1902166) | Cod sursa (job #2094818) | Cod sursa (job #1432603) | Cod sursa (job #2486605)
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct punct
{
int x;
int y;
};
bool comparamX(punct a, punct b)
{
return a.x<b.x;
}
bool comparamY(punct a, punct b)
{
return a.y<b.y;
}
int distanta(punct a, punct b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int min_dist(vector<punct>v, int st, int dr)
{
int m,d1,d2,dist_min,d;
if (dr-st==1)
return distanta(v[st],v[dr]);
if(dr-st==2)
{
int k=distanta(v[st],v[st+1]);
int w=distanta(v[st],v[dr]);
int ww=distanta(v[st+1],v[dr]);
vector <int> mini;
mini.push_back(k);
mini.push_back(w);
mini.push_back(ww);
sort(mini.begin(),mini.end());
return mini[0];
}
m=(st+dr)/2;
d1=min_dist(v,st,m);
d2=min_dist(v,m,dr);
if(d1<d2)
dist_min=d1;
else
dist_min=d2;
// dist_min=min(d1,d2);
int i, j;
d=(int)ceil(sqrt(dist_min));
vector<punct>B;
for(i=st; i<=m-1; i++)
{
if (v[m].x-v[i].x<=d)
B.push_back(v[i]);
}
for(i=m+1; i<=dr; i++)
{
if (v[i].x-v[m].x<=d)
B.push_back(v[i]);
else
break;
}
sort(B.begin(),B.end(),comparamY);
for(i=0; i<B.size(); i++)
{
for(j=i+1; j<=i+7 && j<B.size(); j++)
{
int d3=distanta(v[i],v[j]);
if(dist_min>d3)
dist_min=d3;
}
}
return dist_min;
}
int main()
{
vector <punct> A;
int i, n;
f>>n;
for(i=1; i<=n; i++)
{
punct c;
f>>c.x>>c.y;
A.push_back(c);
}
sort(A.begin(),A.end(),comparamX);
g <<fixed<<setprecision(6) <<sqrt(min_dist(A, 0, n-1));
f.close();
g.close();
}