问题描述

最近点对问题，我用分治写的，和正确的基本一样为什么我的会超时?杭电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(""%.2lfn"" 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;}