Pagini recente » Cod sursa (job #581957) | Cod sursa (job #3188139) | Cod sursa (job #3163634) | Cod sursa (job #933270) | Cod sursa (job #1022315)
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#define Nmax 100001
#define INF 0x3f3f3f
using namespace std;
vector< pair<int,long long> > X,Y, vec,aux;
int N;
void read_data()
{
FILE*f = fopen("cmap.in", "r");
fscanf(f,"%d", &N);
int x,y;
for(int i=0;i<N;++i)
{
fscanf(f,"%d%d", &x,&y);
X.push_back(make_pair(x,y));
}
fclose(f);
}
long long dist(pair<long long, long long> A, pair<long long, long long> B)
{
return (A.first - B.first) * (A.first - B.first) + (A.second - B.second)*(A.second - B.second);
}
long long solve(int left, int right)
{
long long ret;
if(left >= right)
return INF;
if(right - left == 1)
{
if(Y[left] > Y[left + 1])
swap(Y[left], Y[left+1]);
return dist(X[left],X[right]);
}
int mid = (left + right)/2;
ret = min(solve(left, mid), solve(mid, right));
merge(Y.begin() + left, Y.begin() + mid+1, Y.begin() + mid+1, Y.begin() + right+1, vec.begin());
copy(vec.begin(), vec.begin() + (right - left+1), Y.begin()+left);
int size = 0;
for(int i=left;i<=right;++i)
if(abs(X[mid].first - Y[i].second) <= ret)
vec[size++] = Y[i];
for(int i=0;i<size;++i)
for(int j=i+1;j<size && j-i < 8;++j)
ret = min(ret, dist(Y[i], Y[j]));
return ret;
}
int main()
{
read_data();
sort(X.begin(), X.end());
vec.resize(N);
aux.resize(N);
for(int i=0;i<X.size();++i)
Y.push_back(make_pair(X[i].second, X[i].first));
FILE*g = fopen("cmap.out","w");
fprintf(g, "%.6lf\n", sqrt(solve(0, N-1)));
fclose(g);
return 0;
}