Pagini recente » Cod sursa (job #2786680) | Cod sursa (job #827533) | Cod sursa (job #933014) | Cod sursa (job #1244612) | Cod sursa (job #756503)
Cod sursa(job #756503)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
struct TPoint;
typedef TPoint *PPoint;
struct TPoint
{
long X,Y;
};
long N;
TPoint Puncte[100005];
int CompareX(const void *p1,const void *p2)
{
PPoint a = (PPoint)(p1);
PPoint b = (PPoint)(p2);
return a->X - b->X;
}
int CompareY(const void *p1,const void *p2)
{
PPoint a = (PPoint)(p1);
PPoint b = (PPoint)(p2);
return a->Y - b->Y;
}
double mind(double a,double b)
{
if (a < b)
{
return a;
}
return b;
}
double Dist(long a,long b)
{
return sqrt((double)(((Puncte[a].X - Puncte[b].X) * (Puncte[a].X - Puncte[b].X)) +
((Puncte[a].Y - Puncte[b].Y) * (Puncte[a].Y - Puncte[b].Y))));
}
double DM3(long left,long right)
{
long a,b;
double dmin = 1e64;
for (a = left;a <= right;a += 1)
{
for (b = a + 1;b <= right;b += 1)
{
dmin = mind(dmin,Dist(a,b));
}
}
return dmin;
}
double DMX(long left,long right);
double DMY(long left,long right)
{
if ((right - left) <= 3)
{
return DM3(left,right);
}
long mid = left + ((right - left) >> 1);
double dmin = mind(DMY(left,mid),DMY(mid + 1,right));
long leftm,rightm;
double midy = (Puncte[mid].Y + Puncte[mid + 1].Y) / 2;
leftm = mid;
rightm = mid + 1;
while (((midy - Puncte[leftm].Y) < dmin) && (leftm > left))
{
leftm -= 1;
}
while (((Puncte[leftm].Y - midy) < dmin) && (rightm < right))
{
rightm += 1;
}
qsort(Puncte + leftm,rightm - leftm,sizeof(TPoint),CompareX);
dmin = mind(dmin,DMX(leftm,rightm));
return dmin;
}
double DMX(long left,long right)
{
if ((right - left) <= 3)
{
return DM3(left,right);
}
long mid = left + ((right - left) >> 1);
double dmin = mind(DMX(left,mid),DMX(mid + 1,right));
long leftm,rightm;
double midx = (Puncte[mid].X + Puncte[mid + 1].X) / 2;
leftm = mid;
rightm = mid + 1;
while (((midx - Puncte[leftm].X) < dmin) && (leftm > left))
{
leftm -= 1;
}
while (((Puncte[leftm].X - midx) < dmin) && (rightm < right))
{
rightm += 1;
}
qsort(Puncte + leftm,rightm - leftm + 1,sizeof(TPoint),CompareY);
dmin = mind(dmin,DMY(leftm,rightm));
return dmin;
}
int main(void)
{
fstream fin("cmap.in",ios::in);
fstream fout("cmap.out",ios::out);
long i;
fin >> N;
for (i = 0;i < N;i += 1)
{
fin >> Puncte[i].X >> Puncte[i].Y;
}
qsort(Puncte,N,sizeof(TPoint),CompareX);
fout << setprecision(15) << DMX(0,N - 1);
fin.close();
fout.close();
return 0;
}