Pagini recente » Cod sursa (job #3295179) | Cod sursa (job #149709) | Cod sursa (job #2131765) | Cod sursa (job #3268484) | Cod sursa (job #756512)
Cod sursa(job #756512)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;
struct TPoint;
typedef TPoint *PPoint;
struct TPoint
{
long X,Y;
};
long N;
TPoint Puncte[100005];
TPoint Temp[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)
{
double dx = (Puncte[a].X - Puncte[b].X);
double dy = (Puncte[a].Y - Puncte[b].Y);
return sqrt(dx * dx + dy * dy);
}
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 DMY(long left,long right,double dmax)
{
long a,b,c;
double dd;
double dmin = 1e64;
for (a = left;a <= right;a += 1)
{
for (b = (a + 1),c = 0;(b <= right) && (c < 8);b += 1)
{
if ((Puncte[b].X - Puncte[a].X) > dmax)
{
break;
}
dd = Dist(a,b);
if (dd < dmin)
{
dmin = dd;
if (dmin < dmax)
{
dmax = dmin;
}
}
}
}
return dmin;
}
void mergeX(long left,long mid,long right)
{
long d1 = left;
long d2 = mid + 1;
long p = left;
while ((d1 <= mid) && (d2 <= right))
{
if (Puncte[d1].X < Puncte[d2].X)
{
Temp[p] = Puncte[d1];
d1 += 1;
}
else
{
Temp[p] = Puncte[d2];
d2 += 1;
}
p += 1;
}
while (d1 <= mid)
{
Temp[p] = Puncte[d1];
d1 += 1;
p += 1;
}
while (d2 <= right)
{
Temp[p] = Puncte[d2];
d2 += 1;
p += 1;
}
memmove(Puncte + left,Temp + left,sizeof(TPoint) * (right - left + 1));
}
double DMX(long left,long right)
{
if ((right - left) <= 3)
{
qsort(Puncte + left,right - left + 1,sizeof(TPoint),CompareX);
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].Y + Puncte[mid + 1].Y) / 2;
leftm = mid;
rightm = mid + 1;
while (((midx - Puncte[leftm].Y) < dmin) && (leftm > left))
{
leftm -= 1;
}
while (((Puncte[leftm].Y - midx) < dmin) && (rightm < right))
{
rightm += 1;
}
mergeX(left,mid,right);
dmin = mind(dmin,DMY(leftm,rightm,dmin));
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;
}
/* double dmin = 1e64;
for (i = 0;i < N;i += 1)
{
for (long j = 0;j < N;j += 1)
{
if (i == j)
{
continue;
}
dmin = mind(dmin,Dist(i,j));
}
}
fout << setprecision(15) << dmin;*/
qsort(Puncte,N,sizeof(TPoint),CompareY);
fout << setprecision(15) << DMX(0,N - 1);
fin.close();
fout.close();
return 0;
}