DemmonHK 于 2014.11.26 13:58 提问

``````#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;
}
``````