题目
题解
1.我会暴力！：
枚举每两个点距离，取min
O(n^2) 过不了
2.我会分治！：
看到题目数据可以想到将整个点集以类似于归并排序的思路求解
而每个子数组都已处理好，所以只要判断重叠部分的差有没有更小即可
所以我们设已处理好的两个子数组中最小距离为 d
然后设 [l,r] 中间的基准值为 mid (a_{(l+r)/2}) ，对于每一个数，如果x坐标与 mid 的差值 \le d 则 push 到 tmp 中
然后枚举 tmp 中每个元素，对距离取 min ，返回即可
注意：在 3 \le r-l+1 时应使用暴力直接求解
some code:
double solve(int l, int r)
{
if (r - l + 1 <= 3)
{
return bf(l, r);
}
int mid = (l + r) >> 1;
node miid = a[mid];
double d1 = solve(l, mid);
double d2 = solve(mid + 1, r);
double d = min(d1, d2);
vector<node> tmp;
for (int i = l; i <= r; i++)
{
if (fabs(a[i].x - miid.x) < d)
{
tmp.push_back(a[i]);
}
}
sort(tmp.begin(), tmp.end(), cmp2);
double mn = d * d;
for (int i = 0; i < tmp.size(); i++)
{
for (int j = i + 1; j < tmp.size() && (tmp[j].y - tmp[i].y) < d /*若y坐标差值已大于d，直接跳过*/; j++)
{
double dx = tmp[i].x - tmp[j].x;
double dy = tmp[i].y - tmp[j].y;
double d = dx * dx + dy * dy;
mn = min(d, mn);
}
}
return min(d, sqrt(mn));
}