Pagini recente » Cod sursa (job #1654121) | Cod sursa (job #2860506) | Cod sursa (job #941916) | Clasamentul arhivei Infoarena Monthly | Cod sursa (job #2493738)
#include <iostream>
#include<fstream>
#include<vector>
#include<iomanip>
#include <algorithm>
#include <cmath>
using namespace std;
struct punct
{
long long x,y;
};
int cmp(punct x, punct y)
{
return x.x<y.x;
}
void citire(vector<punct>&v,int &n)
{
ifstream fin("cmap.in");
fin>>n;
v.resize(n+1);
for(int i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
fin.close();
}
double distanta(punct x,punct y)
{
int X = x.x - y.x;
int Y = x.y - y.y;
return sqrt(X*X+Y*Y);
}
void interclasare(vector<punct>&v,int st, int mij, int dr)
{
// interclasam dupa Y
vector<punct>aux;
int i = st, j = mij + 1;
while(i <= mij && j <= dr)
{
if(v[i].y < v[j].y)
aux.push_back(v[j++]);
else aux.push_back(v[i++]);
}
while(i<=mij)
{
aux.push_back(v[i++]);
}
while(j<=dr)
{
aux.push_back(v[j++]);
}
for(i = st, j=0; i <= dr; i++,j++)
v[i] = aux[j];
}
double DIVIDE_ET_IMPERA(vector<punct>&v,int st,int dr)
{
int i,j,m;
vector<punct>aux;
if(st == dr)
return 2e18;
if(dr - st == 1) // avem doar 2 puncte
{
// sortam dupa y
if(v[st].y > v[dr].y)
swap(v[st],v[dr]);
return distanta(v[st],v[dr]);
}
m = (st + dr)/2;
// distanta minima intre 2 puncte din fiecare cele 2 parti ale "dreptei"
double dist_min = min(DIVIDE_ET_IMPERA(v,st,m), DIVIDE_ET_IMPERA(v,m+1,dr));
// sortez dupa y, prin interclasare
interclasare(v,st,m,dr);
// tratam cazul in care exista o pereche de puncte situata de o parte si de alta a "dreptei"
// punem in vectorul aux toate punctele situate la distanta maxima dist_min fata de "verticala"
for(i = st; i <= dr; i++)
if(abs(v[i].x - v[m].x) <= dist_min)
{
aux.push_back(v[i]);
}
double mini = 2e18;
for(i = 0; i < aux.size()-1; i++)
for(j = i+1; j < aux.size() && j <= i+8; j++)
mini =min(mini,distanta(aux[i],aux[j]));
return min(mini, dist_min);
}
int main()
{
ofstream fout("cmap.out");
vector<punct>v;
int n;
citire(v,n);
sort(v.begin(),v.end(),cmp);
fout<<fixed<<setprecision(6)<<DIVIDE_ET_IMPERA(v,1,n);
fout.close();
}