洛谷全部全部的“最近点对”题解汇总版

我们都知道曾经大佬 @稻叶昙 反馈过一个有趣的事情那就是这题:
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数据要求:

  1. n \le 50000
  2. n 为正整数
  3. 尽量短

这里说一下,我的代码不是正解,所以不要把我举办。

1 1
1 1000000
1 1000000
1 1000000
若干个
1000000 1
1000000 1
1000000 1
若干个
2 2

稍等不太对

1 1
1 1000000
1 9999995
1 9999990
若干个
1000000 1
999995 1
999990 1
若干个
2 2

答案是 \sqrt{2}

对的

好像没问题,我想想

@2345安全卫士 所以既然题解是错的,为什么还能过审?

之前有人hack的,表面是对的但是有人把所有题解全hack了

这个时候就要再给大家看一位大佬了:
「叉掉第一篇题解」 - 洛谷帖子保存站

1 个赞

我昨晚自己搞了一个

0 0
1 1e9
1 1e9-200
1 1e9-400
1 1e9-600
1 1e9-800
1 1e9-1000
(大概1000个)
1e9 1
1e9-200 1
1e9-400 1
1e9-600 1
1e9-800 1
(大概1000个)
10 10

人类智慧不行啊 记录详情 - 洛谷 | 计算机科学教育新生态
加强版寄了

我这题人类智慧有142

我才140


新纪录