青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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 代碼如下：