Pagini recente » Cod sursa (job #402028) | Cod sursa (job #2041718) | Cod sursa (job #73870) | Cod sursa (job #356665) | Cod sursa (job #2465337)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define x first
#define y second
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n, i, k;
pair<long long, long long> v[100001], a[100001], Y[100001];
long long dist1(int i, int j){
long long f = 1LL*(v[i].x-v[j].x)*(v[i].x-v[j].x) + 1LL*(v[i].y-v[j].y)*(v[i].y-v[j].y);
return f;
}
long long dist2(int i, int j){
return 1LL*(a[i].x-a[j].x)*(a[i].x-a[j].x) + 1LL*(a[i].y-a[j].y)*(a[i].y-a[j].y);
}
int cmp(const pair<long long, long long> &a, const pair<long long, long long> &b){
return a.y<b.y;
}
long long sol(int st, int dr){
if(dr == st+1){
if(v[st].y>v[dr].y)
swap(v[st], v[dr]);
return dist1(st, dr);
}
if(dr == st+2){
sort(v+st+1, v+dr+1, cmp);
return min(dist1(st, st+1), min(dist1(st, st+2), dist1(st+1, st+2)));
}
int mid = (st+dr)/2;
long long d1 = sol(st, mid); /// solutia din stanga
long long d2 = sol(mid+1, dr); /// solutia din dreapta
long long d = min(d1, d2); /// cea mai buna solutie care se afla ba in stanga, ba in dreapta
/// dupa ce mi-am facut treaba in fiecare jumatate
/// fiecare jumatate este sortata dupa y
/// deci le pot interclasa pentru a sorta intregul sir st...dr dupa y
int j = mid+1, t = 0, i=st;
while(i<=mid && j<=dr){
if(v[i].y < v[j].y)
Y[++t] = v[i++];
else
Y[++t] = v[j++];
}
for(;i<=mid;i++)
Y[++t] = v[i];
for(;j<=dr;j++)
Y[++t] = v[j];
int grup = 0;
for(i=st;i<=dr;i++){
v[i] = Y[i-st+1];}
for(i=st;i<=dr;i++){
/// imi aleg ca referinta punctul mid
long long r = v[i].x - v[mid].x;
if(r<0)
r=-r;
if(r <= d)
a[++grup] = v[i];
}
for(i=1;i<grup;i++)
for(j=i+1;j<=i+7 && j<=grup;j++)
d = min(d, dist2(i, j));
return d;
}
int main(){
fin>>n;
for(i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
sort(v+1, v+n+1);
fout<<setprecision(6)<<fixed<<(double)sqrt(sol(1, n));
return 0;
}