Pagini recente » Cod sursa (job #2654872) | Cod sursa (job #3235376) | Cod sursa (job #2493736) | Cod sursa (job #815510) | Cod sursa (job #2493770)
#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 || (x.x == y.x && x.y < y.y));
}
void citire(vector<punct>&v,int &n)
{
ifstream fin("cmap.in");
fin>>n;
v.resize(n);
for(int i=0;i<n;i++)
fin>>v[i].x>>v[i].y;
fin.close();
}
long long distanta(punct x,punct y)
{
int X = x.x - y.x;
int Y = x.y - y.y;
return 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 4e18;
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]);
}
else if(st + 2 == dr) // sunt 3 numere
{
long long mini = 4e18;
for(i=st;i<dr;i++)
for(j=i+1;j<=dr;j++)
mini = min(mini,distanta(v[i],v[j]));
interclasare(v,st,st+1,dr);
return mini;
}
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 = 4e18;
int ssize = aux.size();
for(i = 0; i < ssize-1; i++)
for(j = i+1; j < ssize && j <= i+8; j++)
if(distanta(aux[i],aux[j]) < mini)
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)<<sqrt(DIVIDE_ET_IMPERA(v,0,n-1));
fout.close();
}