我们都知道曾经大佬 @稻叶昙 反馈过一个有趣的事情那就是这题:
P1257 平面上的最接近点对 - 洛谷 (luogu.com.cn)
的题解全部为错解。那么我们再知道,在 @360病毒 的贴子里,提到了一个很“奇葩”的做法。
见 P1429 平面最近点对(加强版) - 洛谷 (luogu.com.cn) 的首个题解内,
明显,这是一种可以过掉的错解。于是在洛谷的另一题 P7883 平面最近点对(加强加强版) - 洛谷 (luogu.com.cn) 内,写着:
那么,我们的周康阳大佬说到:
这时,我们可以想到,这道题的正解其实是分治。
某大佬在他的题解内写到:
接着,老师在课中讲到,这种算法是一定可以被hack掉的只是因为数据水。
所以其实这篇帖子的重点来了,其实这是一篇送解决方案的帖子,只要你可以造出一个hack数据(满足下面代码可以被hack掉),我会给予你一个解决方案。
#include <bits/stdc++.h>
using namespace std;
struct node{
double x,y;
}a[50005];
bool my_cmp(node x,node y){
return x.x<y.x;
}
bool my_cmp2(node x,node y){
return x.y<y.y;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
}
sort(a+1,a+1+n,my_cmp);
double minn=INT_MAX;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n&&j<=i+100;j++){
minn=min(minn,sqrt(pow(a[i].x-a[j].x,2)+pow(a[i].y-a[j].y,2)));
}
}
sort(a+1,a+1+n,my_cmp2);
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n&&j<=i+100;j++){
minn=min(minn,sqrt(pow(a[i].x-a[j].x,2)+pow(a[i].y-a[j].y,2)));
}
}
printf("%.2f",minn);
}
hack数据要求:
- n \le 50000
- n 为正整数
- 尽量短
这里说一下,我的代码不是正解,所以不要把我举办。