Pagini recente » Cod sursa (job #1511386) | Cod sursa (job #1257621) | Cod sursa (job #652491) | Cod sursa (job #1355340) | Cod sursa (job #969142)
Cod sursa(job #969142)
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <ctime>
#include <string>
#include <cstring>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream ff("cmap.in");
ofstream gg("cmap.out");
#define max 100001
int n, k;
struct per{ int x,y; per(int x0=0,int y0=0){x=x0;y=y0;} } ss[max], pp[max];
bool cmp(per a, per b){ return a.x==b.x?a.y<b.y:a.x<b.x; }
double dst(per a, per b){ return sqrt((double)(a.x-b.x)*(a.x-b.x)+(double)(a.y-b.y)*(a.y-b.y)); }
double sol(int s, int d){
if(s>=d) return 0x3f3f3f3f;
if(s==d-1) return dst(ss[s], ss[d]);
int m=(s+d)/2;
double r=min(sol(s,m),sol(m+1,d));
k=0;
for(int i=s;i<=d;i++)
if(abs(ss[i].x-ss[m].x) <= r){
pp[++k]=ss[i];
for(int j=k-1;j>0 && k-j<=7;j--)
r=min(r, dst(pp[k], pp[j]));
}
return r;
}
int main(){
ff >> n;
for(int i=0;i<n;i++) ff >> ss[i].x >> ss[i].y;
sort(ss, ss+n, cmp);
gg << setprecision(10) << fixed << sol(0,n-1) << "\n";
return 0;
}