典型的最近點對算法的應用，不過這個題多了個限制條件，就是點分為2類，最短距離必須在不同的類之間。為了滿足這個限制，只需要
把同類別點直接的距離都當作INF處理即可。
最近點對的算法，算導上面說是nlogn的。但是這個復雜度實現起來略微麻煩點，有一種實現方法是n*logn*logn的，其只對x坐標進行
了排序。n*logn的算法需要對x和y分量分別進行排序，還需要用到其它的輔助數組。
第一個題我用了n*logn算法實現了，第二個題則用了n*logn*logn算法實現了。但是時間上相差不大，因為第一個算法每次進行分治時
候消耗的O(n)時間也有幾次。第二個算法分治時候，需要再次排序的時間也不一定很多，因為可能數據量不夠大。
算法的本質就是二分按照X排序好的點數組，n*logn*logn變成n*logn的關鍵是預先對y也排序好一個點數組，因為按y排序好的點數組，
在分治後的合並中要用到。算法更詳細的解釋請參照算法導論。
poj 3714 代碼如下：
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define MAX_N (100000 * 2 + 10)
const double FINF = 1LL << 60;
struct Point
{
double x, y;
int nKind;
};
Point pts[MAX_N], ptsY[MAX_N], ptsTemp[MAX_N];
Point ptsSave[MAX_N];
int nNum;
bool CmpX(const Point& a, const Point& b)
{
return a.x < b.x;
}
bool CmpY(const Point& a, const Point& b)
{
return a.y < b.y;
}
double Dis(Point a, Point b)
{
if (a.nKind == b.nKind)
{
return FINF;
}
else
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
}
double FindMinDis(Point pts[], Point ptsY[], Point ptsTemp[], int nBeg, int nEnd)
{
if (nBeg == nEnd)
{
return FINF;
}
else if (nBeg + 1 == nEnd)
{
return Dis(pts[nBeg], pts[nEnd]);
}
else if (nBeg + 2 == nEnd)
{
return min(min(Dis(pts[nBeg], pts[nBeg + 1]), Dis(pts[nBeg], pts[nEnd])),
Dis(pts[nBeg + 1], pts[nEnd]));
}
else
{
memcpy(ptsSave + nBeg, ptsY + nBeg, sizeof(Point) * (nEnd - nBeg + 1));//保存當前的Y坐標順序
int nMid = (nBeg + nEnd) / 2;
int nL = nBeg;
int nR = nMid + 1;
for (int i = nBeg; i <= nEnd; ++i)
{
if (ptsY[i].x - pts[nMid].x <= 0)
{
ptsTemp[nL++] = ptsY[i];
}
else
{
ptsTemp[nR++] = ptsY[i];
}
}
double fAns = min(FindMinDis(pts, ptsTemp, ptsY, nBeg, nMid),
FindMinDis(pts, ptsTemp, ptsY, nMid + 1, nEnd));
int nK = 1;
for (int i = nBeg; i <= nEnd; ++i)
{
if (fabs(ptsSave[i].x - pts[nMid].x) <= fAns)
{
ptsTemp[nK++] = ptsSave[i];
}
}
for (int i = 1; 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[i], ptsTemp[j]));
}
}
return fAns;
}
}
int main()
{
int nT;
int nN;
//printf("%f", FINF);
scanf("%d", &nT);
while (nT--)
{
scanf("%d", &nN);
nNum = nN * 2;
for (int i = 0; i < nN; ++i)
{
scanf("%lf%lf", &pts[i].x, &pts[i].y);
pts[i].nKind = 1;
}
for (int i = nN; i < nNum; ++i)
{
scanf("%lf%lf", &pts[i].x, &pts[i].y);
pts[i].nKind = 2;
}
memcpy(ptsY, pts, sizeof(Point) * nNum);
sort(pts, pts + nNum, CmpX);
sort(ptsY, ptsY + nNum, CmpY);
printf("%.3f\n", FindMinDis(pts, ptsY, ptsTemp, 0, nNum - 1));
}
return 0;
}
hdu 1007 代碼如下：
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define MAX (100000 + 10)
struct Point
{
double x, y;
};
Point pts[MAX];
Point ptsTemp[MAX];
const double FINF = 1LL << 60;
bool CmpX(const Point& a, const Point& b)
{
return a.x < b.x;
}
bool CmpY(const Point& a, const Point& b)
{
return a.y < b.y;
}
double Dis(Point a, Point b)
{
return sqrt((a.x - b.x) * (a.x - b.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;
}
