2 demmonhk DemmonHK 于 2014.11.26 13:58 提问

最近点对问题,我用分治写的,和正确的基本一样为什么我的会超时?杭电1007

高手帮忙看看,已经弄了很长时间了还是看不出来哪里有问题,感觉写得和网上的一样呀。

#include<iostream>
#include<cmath>
using namespace std;
void kuaipai(double*, double*, int, int);
double zuijindian(double*, double*, int, int);
double x[100000], y[100000], temx[100000], temy[100000];
int main()
{
    int n;
    while (cin >> n&&n != 0)
    {
        for (int i = 0; i<n; i++)
        {
            cin >> x[i];
            cin >> y[i];
        }
        kuaipai(x, y, 0, n - 1);
        printf("%.2lf\n", sqrt(zuijindian(x, y, 0, n - 1)) / 2);
    }

}
void kuaipai(double* x, double*y, int p, int r)
{
    double m = x[r];
    double t;
    int i = p - 1;
    if (p < r)
    {
        for (int j = p; j < r; j++)
        {
            if (x[j] < m)
            {
                i++;
                t = x[i];
                x[i] = x[j];
                x[j] = t;
                t = y[i];
                y[i] = y[j];
                y[j] = t;

            }
        }
        x[r] = x[i + 1];
        x[i + 1] = m;
        t = y[r];
        y[r] = y[i + 1];
        y[i + 1] = t;
        kuaipai(x, y, p, i);
        kuaipai(x, y, i + 2, r);
    }
}


double zuijindian(double*x, double*y, int p, int r)
{

    int m;
    double d, d_, t, d1, d2;
    if (p == r) //如果有一个点
    {
        return 0;
    }
    if (r - p == 1)//如果有两个点
    {
        d = (x[p] - x[r])*(x[p] - x[r]) + (y[p] - y[r])*(y[p] - y[r]);
        return d;
    }
    if (r - p == 2)//如果有三个点
    {
        d = (x[p] - x[r])*(x[p] - x[r]) + (y[p] - y[r])*(y[p] - y[r]);
        d1 = (x[p + 1] - x[r])*(x[p + 1] - x[r]) + (y[p + 1] - y[r])*(y[p + 1] - y[r]);
        d2 = (x[p + 1] - x[p])*(x[p + 1] - x[p]) + (y[p + 1] - y[p])*(y[p + 1] - y[p]);
        if (d>d1)
        {
            d = d1;
        }
        if (d>d2)
        {
            d = d2;
        }
        return d;
    }
    m = (p + r) / 2;//分治
    d1 = zuijindian(x, y, p, m);
    d2 = zuijindian(x, y, m + 1, r);
    if (d1<d2)
    {
        d = d1;
        d_ = sqrt(d1);
    }
    else {
        d_ = sqrt(d2);
        d = d2;
    }
    int  k = 0;
    for (int i = m - 1; i >= 0 && fabs(x[m] - x[i]) <= d_; i--)//接下来两个for搜索分界相邻长度为d_的区域里的点
    {


        temx[k] = x[i];
        temy[k] = y[i];
        k++;

    }
    for (int i = m; i <= r && fabs(x[m] - x[i]) <= d_; i++)
    {


        temx[k] = x[i];
        temy[k] = y[i];
        k++;

    }
    kuaipai(temy, temx, 0, k - 1);
    for (int i = 0; i<k; i++)//比较中间区域的点
    {
        for (int j = i + 1; j < k&&fabs(temy[j] - temy[i]) < d_; j++)
        {
            t = (temy[i] - temy[j])* (temy[i] - temy[j]) + (temx[i] - temx[j])*(temx[i] - temx[j]);
            if (d>t)
            {
                d = t;
            }

        }

    }
    return d;
}
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!