希望可以举一些例子,比较形象简单的(球球了
一些严谨的数学证明也可以/se
for (int i = 1, pl = 1, pr = 1; i <= ca; i++) {
for (; pr <= cb && (b[pr].second - a[i].second) * (b[pr].second - a[i].second) < ans; pr++) {
}
for (; pl <= cb && a[i].second-b[pl].second >= 0 && (a[i].second - b[pl].second) * (a[i].second - b[pl].second) >= ans; pl++) {
}
// for (; pl <= cb && (a[i].second - b[pl].second) * (a[i].second - b[pl].second) >= ans; pl++) {
// }
for (int j = pl; j < pr && j <= cb; j++) {
D(a[i], b[j]);
}
用注释掉的部分替代上一条语句会WA,这是为什么呢?
按道理来说,既然y方向的差的平方已经超过最近距离的平方ans,就不能贡献答案了,注释部分替代应该不会对最终结果造成影响呀
AC代码-1
这份代码是直接用最短距离ans的,但是为什么他的下界是这样子
for (int i = 1, pl = 1, pr = 1; i <= ca; i++) {
for (; pr <= cb && b[pr].second - a[i].second < ans; pr++) {
}
for (; pl <= cb && a[i].second - b[pl].second >= ans; pl++) {
}
// for (; pl <= cb && fabs(a[i].second - b[pl].second) >= ans; pl++) {
// }
for (int j = pl; j < pr; j++) {
D(a[i], b[j]);
}
}
如果用注释掉的部分替代,也是会WA,
按道理来说,既然y方向的差的绝对值已经超过最近距离ans,就不能贡献答案了,注释部分替代应该不会对最终结果造成影响呀