Pagini recente » Cod sursa (job #2472948) | Cod sursa (job #1684958)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#define pb push_back
#define mp make_pair
#define MAXN 100001
#define INFILE "cmap.in"
#define OUTFILE "cmap.out"
#define inf 4e18
#define pct pair<long long,long long>
#define x first
#define y second
using namespace std;
ifstream f(INFILE);
ofstream g(OUTFILE);
int n,i,a,b;
pct c[MAXN],v[MAXN];
inline bool comp(const pct&a,const pct& b)
{
if(a.y==b.y)return a.x<b.x;
return a.y<b.y;
}
inline bool compare(const pct&a, const pct& b)
{
if(a.x==b.x)return a.y<b.y;
return a.x<b.x;
}
double dist(int st, int dr)
{
if(dr-st>3)
{
int m=(st+dr)/2;
double mn=min(dist(st,m),dist(m,dr));
int k=0,i,j;
double C=(v[m].x+v[m-1].x)/2;
i=m-1;
while(C-v[i].x<=mn&&i>=st)
c[k++]=v[i--];
i=m;
while(v[i].x-C<=mn&&i<dr)
c[k++]=v[i++];
sort(c,c+k,comp);
for(i=0;i<k-1;i++)
for(j=i+1;j<=i+8&&j<k;++j)
mn=min(mn,sqrt((c[j].x-c[i].x)*(c[j].x-c[i].x)+(c[j].y-c[i].y)*(c[j].y-c[i].y)));
return mn;
}
double mn=1e9;
int i,j;
for(i=st;i<dr-1;i++)
for(j=i+1;j<dr;j++)
mn=min(mn,sqrt((v[j].x-v[i].x)*(v[j].x-v[i].x)+(v[j].y-v[i].y)*(v[j].y-v[i].y)));
return mn;
}
int main()
{
f>>n;
for(i=0;i<n;i++)
f>>v[i].x>>v[i].y;
sort(v,v+n,compare);
g<<fixed<<setprecision(6)<<dist(0,n);
f.close();
g.close();
return 0;
}