Pagini recente » Cod sursa (job #3258484) | Cod sursa (job #3210115) | Cod sursa (job #444047) | Cod sursa (job #1070848) | Cod sursa (job #1623600)
#include <vector>
#include <cmath>
#include <fstream>
#include <iomanip>
#include <algorithm>
#define NMAX 100005
#define INF 1000000000000000000
using namespace std;
vector <pair <long long,long long > >v,u,S;
inline long long min(long long a,long long b){
if (a<=b)return a;
return b;
}
inline long long dist(const pair <long long,long long >& a,const 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 dei(int st,int dr){
if (st==dr)return INF;
if (st+1==dr){
if (u[st]>u[dr])swap(u[st],u[dr]);
return dist(u[st],u[dr]);
}
int m=(st+dr)/2;
long long val1=dei(st,m);
long long val2=dei(m+1,dr);
long long sol=min(val1,val2);
sort(u.begin()+st,u.begin()+dr+1);
int nr=0;
for (int i=st;i<=dr;i++)if (abs(u[i].second-v[m].first)<=sol)S[++nr]=u[i];
for (int i=1;i<=nr;i++)
for (int j=i+1;j<=nr && j-i<=7;j++){
long long distance=dist(S[i],S[j]);
sol=(sol<distance?sol:distance);
}
return sol;
}
int main()
{
ifstream f("cmap.in");
ofstream g("cmap.out");
int n;
f>>n;
v.resize(n+1);u.resize(n+1);S.resize(n+1);
for (int i=1;i<=n;i++){
f>>v[i].first>>v[i].second;
u[i].first=v[i].second;
u[i].second=v[i].first;
}
sort(v.begin(),v.end());
g<<fixed<<setprecision(6)<<(double)sqrt((long long) dei(1,n));
fclose(stdin);
fclose(stdout);
}