Pagini recente » Cod sursa (job #866291) | Cod sursa (job #2276042) | Cod sursa (job #2371291) | Cod sursa (job #582941) | Cod sursa (job #2491261)
#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, vector<punct> vv, 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;
punct mij=v[m];
vector <punct> Vstg;
vector <punct> Vdr;
int i;
for(i=st;i<=dr;i++)
if (vv[i-st].x<=mij.x)
Vstg.push_back(vv[i]);
else
Vdr.push_back(vv[i]);
d1=min_dist(v,Vstg,st,m);
d2=min_dist(v,Vdr,m+1,dr);
if(d1<d2)
dist_min=d1;
else
dist_min=d2;
// dist_min=min(d1,d2);
int j;
d=(int)ceil(sqrt(dist_min));
vector<punct>B;
for(i=st; i<=m-1; i++)
{
if (vv[m].x-vv[i-st].x<=d)
B.push_back(vv[i]);
}
for(i=m+1; i<=dr; i++)
{
if (vv[i-st].x-vv[m].x<=d)
B.push_back(vv[i]);
else
break;
}
for(i=0; i<B.size(); i++)
{
for(j=i+1; j<=i+7 && j<B.size(); j++)
{
int d3=distanta(vv[i],vv[j]);
if(dist_min>d3)
dist_min=d3;
}
}
return dist_min;
}
int main()
{
vector <punct> A;
vector <punct> K;
int i, n;
f>>n;
for(i=1; i<=n; i++)
{
punct c;
f>>c.x>>c.y;
A.push_back(c);
K.push_back(c);
}
sort(A.begin(),A.end(),comparamX);
sort(K.begin(),K.end(),comparamY);
g <<fixed<<setprecision(6) <<sqrt(min_dist(A,K, 0, n-1));
f.close();
g.close();
}