Pagini recente » Cod sursa (job #1750587) | Cod sursa (job #395800) | Cod sursa (job #274624) | Cod sursa (job #2433736) | Cod sursa (job #2068369)
#include <iostream>
#include <vector>
#include <fstream>
#include <cmath>
#include <stdlib.h>
#include <algorithm>
#include <iomanip>
#include <float.h>
using namespace std;
ifstream fin;
ofstream fout;
struct punct
{
int x,y;
};
bool comp1(punct a,punct b)
{
return (a.x < b.x);
}
bool comp2(punct a,punct b)
{
return (a.y < b.y);
}
double d(punct a,punct b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double Distanta(vector<punct> v,vector<punct> w,int st,int dr)
{
if (dr-st == 1)
return d(v[st],v[dr]);
if (dr-st == 2)
return min(min(d(v[st],v[st+1]),d(v[st+1],v[dr])),d(v[st],v[dr]));
double dist;
int m = (st+dr)/2;
double d1 = Distanta(v,w,st,m);
double d2 = Distanta(v,w,m+1,dr);
dist = min(d1,d2);
vector <punct> aux;
for (int i=st;i<dr;i++)
if (abs(w[i].x - w[m].x) < dist)
aux.push_back(w[i]);
double d3 = DBL_MAX;
for (int i=0;i<aux.size();i++)
{
int j = i+1;
while ((j <= i+7) && (j < aux.size()))
{
d3 = min(d3,d(w[i],w[j]));
j++;
}
}
dist = min(dist,d3);
return dist;
}
int main()
{
vector <punct> punctex,punctey;
fin.open("cmap.in");
int n;
fin >> n;
for(int i=0;i<n;i++)
{
punct a;
fin >> a.x >> a.y;
punctex.push_back(a);
}
fin.close();
punctey = punctex;
sort(punctex.begin(),punctex.end(),comp1);
sort(punctey.begin(),punctey.end(),comp2);
fout.open("cmap.out");
fout << fixed << setprecision(6) << Distanta(punctex,punctey,0,n-1);
fout.close();
return 0;
}