Pagini recente » Cod sursa (job #2408058) | Cod sursa (job #1421395) | Cod sursa (job #534284) | Cod sursa (job #1772506) | Cod sursa (job #2465326)
#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<int, int> v[100001], a[100001], Y[100001];
int dist1(int i, int j){
return (v[i].x-v[j].x)*(v[i].x-v[j].x) + (v[i].y-v[j].y)*(v[i].y-v[j].y);
}
int dist2(int i, int j){
return (a[i].x-a[j].x)*(a[i].x-a[j].x) + (a[i].y-a[j].y)*(a[i].y-a[j].y);
}
int sol(int st, int dr){
if(dr == st+1){
return dist1(st, dr);
}
if(dr == st+2){
return min(dist1(st, st+1), min(dist1(st, st+2), dist1(st+1, st+2)));
}
int mid = (st+dr)/2;
int d1 = sol(st, mid); /// solutia din stanga
int d2 = sol(mid+1, dr); /// solutia din dreapta
int 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];
if(dist1(i, mid) <= d) /// imi aleg ca referinta punctul mid
a[++grup] = v[i];
}
for(i=1;i<=grup-7;i++)
for(j=i+1;j<=i+7;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(7)<<fixed<<(double)sqrt(sol(1, n));
return 0;
}