Pagini recente » Cod sursa (job #3263091) | Cod sursa (job #1164049) | Cod sursa (job #154022) | Cod sursa (job #3283168) | Cod sursa (job #408019)
Cod sursa(job #408019)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <math.h>
using namespace std;
#define nmax 100001
struct punct { int x,y;};
punct v[nmax];
int n;
double cmp(punct p1, punct p2)
{
return p1.x<=p2.x;
}
double dist (punct p1, punct p2)
{
return sqrt(pow((double)p1.x-p2.x,2.0) + pow((double)p1.y-p2.y,2.0));
}
double distmin(int st, int dr)
{
if (dr - st <= 2)
{
if (dr==st+1)
return dist(v[st], v[dr]);
if (dr==st+2)
{
double mini = dist(v[st],v[st+1]);
double d2 = dist(v[dr],v[st+1]);
double d3 = dist(v[st],v[dr]);
if (mini > d2)
mini = d2;
if (mini > d3)
mini = d3;
return mini;
}
}
else
{
int j,i,ls,ld;
int mj = (st+dr)/2;
double d = distmin(st,mj);
double d2 = distmin(mj+1,dr);
if (d > d2)
d = d2;
for (i=mj;i>=0;i--)
if (v[mj].x - v[i].x > d)
break;
ls = i+1;
for (i=mj+1;i<n;i++)
if (v[i].x - v[mj+1].x > d)
break;
ld = i-1;
for (i=ls;i<=mj;i++)
for (j=mj+1;j<=ld;j++)
{
double d1 = dist(v[i],v[j]);
if ( d1 < d)
d = d1;
}
return d;
}
}
int main()
{
int i;
ifstream fin("cmap.in");
fin>>n;
for (i=0;i<n;i++)
fin >> v[i].x>>v[i].y;
sort(v,v+n,cmp);
cout<<fixed<<setprecision(6);
cout<<distmin(0,n-1);
ofstream fout("cmap.out");
fout<<fixed<<setprecision(6);
fout<<distmin(0,n-1);
return 0;
}