poj 3714 Raid and hdu 1007 Quoit Design(二)

2014-11-24 11:37:50 · 作者: · 浏览: 2
.x) + (b.y - a.y) * (b.y - a.y));
}

double Find(int nL, int nH)
{
if (nL == nH)
{
return FINF;
}
else if (nL + 1 == nH)
{
return Dis(pts[nL], pts[nH]);
}
else if (nL + 2 == nH)
{
return min(Dis(pts[nL], pts[nL + 1]),
min(Dis(pts[nL], pts[nH]), Dis(pts[nH], pts[nL + 1])));
}
else
{
int nMid = (nL + nH) / 2;
double fAns = min(Find(nL, nMid), Find(nMid + 1, nH));
int nK = 0;
for (int i = nL; i <= nH; ++i)
{
if (fabs(pts[i].x - pts[nMid].x) <= fAns)
{
ptsTemp[nK++] = pts[i];
}
}
sort(ptsTemp, ptsTemp + nK, CmpY);
for (int i = 0; i < nK; ++i)

{
for (int j = i + 1; j < nK; ++j)
{
if (ptsTemp[j].y - ptsTemp[i].y >= fAns)
{
break;
}
fAns = min(fAns, Dis(ptsTemp[j], ptsTemp[i]));
}
}

return fAns;
}
}

int main()
{
int nN;

while (scanf("%d", &nN), nN)
{
for (int i = 0; i < nN; ++i)
{
scanf("%lf%lf", &pts[i].x, &pts[i].y);
}
sort(pts, pts + nN, CmpX);
printf("%.2f\n", Find(0, nN -1) * 0.5);
}

return 0;
}