Pagini recente » Cod sursa (job #277305) | Cod sursa (job #2333165) | Cod sursa (job #1445688) | Cod sursa (job #250987) | Cod sursa (job #1022303)
#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;
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));
sort(Y.begin() + left, Y.begin() + right);
vec.clear();
for(int i=left;i<=right;++i)
if(abs(X[mid].first - Y[i].second) <= ret)
vec.push_back(Y[i]);
for(int i=0;i<vec.size();++i)
for(int j=i+1;j<vec.size() && j-i < 8;++j)
ret = min(ret, dist(Y[i], Y[j]));
return ret;
}
int main()
{
read_data();
sort(X.begin(), X.end());
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;
}