Pagini recente » Statistici Stefan Timisescu (Stefantim) | Rezultatele filtrării | Cod sursa (job #1092129) | Diferente pentru propuneri/6-arhiva-educationala intre reviziile 14 si 16 | Cod sursa (job #408075)
Cod sursa(job #408075)
#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)
{
double d = dist(v[st], v[dr]);
//cout<<st<<' '<<dr<<' '<<d<<endl;
return d;
}
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;
//cout<<st<<' '<<dr<<' '<<mini<<endl;
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>=st;i--)
if (v[mj].x - v[i].x > d)
break;
ls = i+1;
for (i=mj+1;i<=dr;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;
}
//cout<<st<<' '<<dr<<' '<<ls<<' '<<mj<<' '<<ld<<endl;
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;
//v[i].x/=100000;
//v[i].y/=100000;
}
sort(v,v+n,cmp);
//for (i=0;i<n;i++)
// cout<<i<<':'<<v[i].x<<' '<<v[i].y<<'\t';
//cout<<endl;
//cout<<fixed<<setprecision(6);
//cout<<distmin(0,n-1)<<endl;
ofstream fout("cmap.out");
fout<<fixed<<setprecision(6);
fout<<distmin(0,n-1)<<endl;;
return 0;
}