// 下面是我写的程序
// 当n=1000,000时，耗时1.3秒左右（主要时间花在排序上了）
typedef struct  
{
    int        x, y;
    double    dist;
}Point;

inline double GetDist(int x1, int y1, int x2, int y2)
{
    return sqrt(((double)x2-x1)*(x2-x1)+((double)y2-y1)*(y2-y1));
}

// 求(p1-p0)和(p2-p0)的叉积
inline double CrossProduct(int x0, int y0, int x1, int y1, int x2, int y2)
{
    return ((x1-x0)*(y2-y0)-(x2-x0)*(y1-y0));
}

// 判断点(x0,y0)是否在其他三点组成的三角形内，并判断三角形的有效性
bool PtInTriangle(int x0, int y0, int x1, int y1, int x2, int y2, int x3, int y3)
{
    double        cp1, cp2;
    
    cp1 = CrossProduct(x0, y0, x1, y1, x2, y2);
    cp2 = CrossProduct(x0, y0, x1, y1, x3, y3);
    
    if(cp1 * cp2 < 0)    // 点p2或p3在p0p1直线的两边，允许
    {
        cp1 = CrossProduct(x2, y2, x3, y3, x0, y0);
        cp2 = CrossProduct(x2, y2, x3, y3, x1, y1);
        if(cp1 * cp2 > 0)    // 点p0和p1位于直线p2p3的同一边，允许
            return 1;        // 此时实际上p0还不一定在三角形p1p2p3内；但如果不在三角形内，必定有p0的x或者y坐标大于所有的三个点p1p2p3的x或者y坐标            
        else if(cp1    == 0 && cp2 != 0)        // 点p0在p2p3上
            return 1;
        else
            return 0;
    }
    else if(cp1 == 0 && cp2 != 0)
    {
        if((x1-x0)*(x0-x2) > 0 || (y1-y0)*(y0-y2) > 0    // 点p0在p1p2线段上
                || x0 == x2 && y0 == y2)                // 点p0与p2重合
            return 1;        // 
    }
    else if(cp1 != 0 && cp2 == 0)
    {
        if((x1-x0)*(x0-x3) > 0 || (y1-y0)*(y0-y3) > 0    // 点p0在p1p3线段上
                || x0 == x3 && y0 == y3)                // 点p0与p3重合
            return 1;        // 
    }
    else if(cp1 == 0 && cp2 == 0)
    {
        if(x0 == x1 && y0 == y1            // p0与p1重合
                && (x1 != x2 || y1 != y2)    // p1 != p2
                && (x1 != x3 || y1 != y3)    // p1 != p3
                && (x2 != x3 || y2 != y3))    // p2 != p3
            return 1;
    }

    return 0;
}
// 用于快速排序
int cmp(const void *x1, const void *x2)
{
    Point        a = *(Point *)x1;
    Point        b = *(Point *)x2;

    if(a.dist >= b.dist)
        return 1;
    else
        return -1;
}

double MinDistance(int x[], int y[], int n, int x0, int y0, char *id)
{
    Point        *points = new Point[n];
    assert(points);

    int            i, j, k;
    double        distMin = DBL_MAX, dist, distExit;
    int            minx = INT_MAX, maxx = -INT_MAX, miny = INT_MAX, maxy = -INT_MAX;
    for(i=0; i<n; ++i)
    {
        points[i].x = x[i];
        points[i].y = y[i];
        points[i].dist = GetDist(x0, y0, x[i], y[i]);

        if(minx > x[i])
            minx = x[i];
        if(maxx < x[i])
            maxx = x[i];
        if(miny > y[i])
            miny = y[i];
        if(maxy < y[i])
            maxy = y[i];
    }
    if(x0 < minx || x0 > maxx || y0 < miny || y0 > maxy)
        goto end;

    qsort(points, n, sizeof(Point), cmp);

    // 从距离最小的三个点开始进行考察
    // 这儿看起来有三重循环，但实际上由于是随机分布的点，极端情况出现的概率是非常低的。
    // 因此大部分情况下，该三重循环的循环次数都很少。我实际测试了一下，当n=1000,000时，
    // 最内循环的次数绝大部分情况都少于1000次。
    for (i=2; i<n; i++)
    {
        distExit = points[0].dist + points[1].dist + points[i].dist;    
        for(j=0; j<i-1; j++)
        {
            for(k=j+1; k<i; k++)
            {
                // 排除明显不合适的三角形
                if(x0 > points[i].x && x0 > points[j].x && x0 > points[k].x)
                    continue;
                if(x0 < points[i].x && x0 < points[j].x && x0 < points[k].x)
                    continue;
                if(y0 > points[i].y && y0 > points[j].y && y0 > points[k].y)
                    continue;
                if(y0 > points[i].y && y0 > points[j].y && y0 > points[k].y)
                    continue;

                if(PtInTriangle(x0, y0, points[i].x, points[i].y, points[j].x, points[j].y, points[k].x, points[k].y))
                {
                     dist = points[i].dist + points[j].dist + points[k].dist;
                    if(distMin > dist)
                        distMin = dist;
                    if(distMin <= distExit)
                        goto end;
                } 
            } 
        }
    }

end:
    delete []points;

    return distMin!=DBL_MAX?distMin:0;
}

[quote]// 下面是我写的程序
// 当n=1000,000时，耗时1.3秒左右（主要时间花在排序上了）
[/quote]

这个是怎么测出来的???我如果想自己测代码效率什么的要怎么测???

用clock()函数或者GetTickCount（）
函数调用前后的时间相减即可

这样得出的结果不是很准确啊，因为还需要考虑环境的影响问题。

如果测第一个的时候，KAV没扫描；二测第二个的时候，KAV开始扫描，那两者的差距就大啦~

另外，如果代码量大，函数很多，那么每个函数调用弄一个 clock来减，这样的方法似乎不妥。

当然这样能得到一个大概的结果，我只是想找到一个更精确，更有效率的办法。

如果 LZ有兴趣一起讨论的话，请到我发的帖子，大家一起研究一下，如果LZ有更好的方法，就请赐教。

http://bbs.pfan.cn/post-281523.html  (测试程序效率的方法)

是的，不精确，受到很多因素的干扰，呵呵。比如软硬件环境，测试时机，编译器，编译模式等等。
但是，一个是没有必要太精确，对于大量的代码也没必要每个函数都要去测试他的时间消耗，你需要测试的也只是关键的部分而已。而且很多时候通过分析代码就可以很容易确定他的时间复杂度，这个可能比实际测试更准确。如果你实在需要那么精确，可以去分析每个函数所用的指令数（这个一是很难，另外也不一定太准确，因为同样的代码不同编译器得到的指令数也不一样），Donald.E.Knuth在他的《计算机程序设计艺术》一书中，分析算法时，就精确到了指令的条数，呵呵。

[quote]是的，不精确，受到很多因素的干扰，呵呵。比如软硬件环境，测试时机，编译器，编译模式等等。
但是，一个是没有必要太精确，对于大量的代码也没必要每个函数都要去测试他的时间消耗，你需要测试的也只是关键的部分而已。而且很多时候通过分析代码就可以很容易确定他的时间复杂度，这个可能比实际测试更准确。如果你实在需要那么精确，可以去分析每个函数所用的指令数（这个一是很难，另外也不一定太准确，因为同样的代码不同编译器得到的指令数也不一样），Donald.E.Knuth在他的《计算机程序设计艺术》一书中，分析算法时，就精确到了指令的条数，呵呵。[/quote]


此贴应评 30分

楼主能把产生随机数的程序 和一些测试数据发出来吗?谢谢!

因为都是随机数据，发出来是没意义的，我也没特意保存哪一份数据，呵呵。至于产生的程序，其实就是不断调用rand()来生成x,y的坐标而已。当然在之前需要用srand初始化一下。回帖的网友中有两个的main函数就有代码。

晕了，没想到是我啊，当时写完程序测试时我就知道玩完，n值大了跑的太慢了，想着要对得起花费的时间就把它传上来了……还得向各位多学习啊，关于出题，谁能教教我呢？有什么规则 新手啊新手