Pagini recente » Cod sursa (job #2580670) | Cod sursa (job #3252575) | Cod sursa (job #1214125) | Cod sursa (job #3252580) | Cod sursa (job #1021529)
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <iomanip>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
long long minim;
struct punct
{
int x,y;
};
vector<punct> lista;
vector<punct> s;
bool cmp(punct a, punct b)
{
return a.x < b.x;
}
bool cmp2(punct a, punct b)
{
return a.y < b.y;
}
double dist(int x, int y)
{
return sqrt(1ll*(lista[x].x - lista[y].x)*(lista[x].x - lista[y].x)+ 1ll*(lista[x].y - lista[y].y)*(lista[x].y - lista[y].y));
}
double dist1(int x, int y)
{
return sqrt(1ll*(s[x].x - s[y].x)*(s[x].x - s[y].x)+ 1ll*(s[x].y - s[y].y)*(s[x].y - s[y].y));
}
double dmin(int xz, int yz){
if(yz - xz <= 2 && yz-xz!=0){
double ddmin;
ddmin = dist(xz,yz);
if(xz + 1 < yz) {
double aux;
aux = dist( xz, xz+1);
if(aux < ddmin) ddmin = aux;
aux = dist( xz+1, yz);
if(aux < ddmin) ddmin = aux;
}
return ddmin;
}
else {
double s1,s2, s0;
int a,b,c;
a = (xz + yz)/2;
c = a;
b = a+1;
s1 = dmin( xz, a);
s2 = dmin( b, yz);
s0 = s1 < s2 ? s1 : s2;
while(a >= xz && lista[c].x - lista[a].x <= s0){s.push_back(lista[a]); a--;}
while(b <= yz && lista[b].x - lista[c].x <= s0){s.push_back(lista[b++]); b++;}
sort(s.begin(), s.end(), cmp2);
int l = s.size();
for (int i = 0; i < l; ++i)
for (int j = i + 1; j < l && (j - i) < 8; j++) {
{
double x;
x = dist1(i,j);
if( x < s0) s0 = x;
}
}
s.clear();
return s0;
}
}
int main()
{
int N;
fin>>N;
for(int i = 0; i < N; i++)
{
punct aux;
fin>>aux.x>>aux.y;
lista.push_back(aux);
}
sort(lista.begin(), lista.end(), cmp);
fout<< setprecision(20)<<dmin(0,N-1);
return 0;
}