Pagini recente » Cod sursa (job #1873548) | Cod sursa (job #2000523) | Cod sursa (job #2304189) | Cod sursa (job #1168119) | Cod sursa (job #1364079)
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iomanip>
//cele mai apropiate puncte in plan
using namespace std;
double inf = 10000000000000000;
inline double sqr(double x)
{
return x*x;
}
struct punct{
double x, y;
};
int n;
double dist(punct q, punct w)
{
return sqrt( sqr(q.x-w.x) + sqr(q.y-w.y) );
}
double min_dist(punct *A, int left, int right) {
if(left == right) return inf;
if(left+1 == right) return dist(A[left], A[right]);
int mid = (left+right)/2;
double dist1 = min(min_dist(A, left, mid), min_dist(A, mid+1, right));
vector <punct> Y;
for(int i = left; i <= right; i++) {
if( dist(A[i], A[mid]) < dist1 ) {
Y.push_back(A[i]);
}
}
for(int i = 0; i < Y.size(); i++ ){
for(int j = i+1; j < Y.size() && i+7 > j; j++) {
if( dist(Y[i], Y[j]) < dist1 ) {
dist1 = dist(Y[i], Y[j]);
}
}
}
return dist1;
}
bool cmp(punct q, punct w)
{
return q.x <= w.x;
}
int main()
{
ifstream inFile("cmap.in");
ofstream outFile("cmap.out");
inFile >> n;
punct A[100004];
double x, y;
punct p;
for(int i = 1; i <= n; i++) {
inFile >> x >> y;
p.x = x;
p.y = y;
A[i] = p;
}
sort(A+1, A+1+n, cmp);
outFile << fixed << setprecision(6) << min_dist(A, 1, n);
}