乱搞

原题链接：21452.平面上的最接近点对

暑假神（开学祭

2024-06-16 21:35:53

发布于：上海

26阅读

0回复

0点赞

我们充分发扬人类智慧：
将所有点全部绕原点旋转同一个角度，然后按 $x$ 坐标排序。
根据数学直觉，在随机旋转后，答案中的两个点在数组中肯定不会离得太远。
所以我们只取每个点向后的 $5$ 个点来计算答案。
这样速度快得飞起，在 $n=1000000$ 时都可以在 1s 内卡过。

-- By 某 Luogu 大佬--

洛谷原题：P1257 平面上的最接近点对
我们飞快地写出了：（AC，38ms）

#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <ctime>
using namespace std;

#define ri register int
#define inf 1000000000000000000

struct pos{
	long double x, y;
}a[400005];
int n;
bool cmp(pos x,pos y){return x.x*x.y<y.x*y.y;}

#define read(x) {\
	x=0;\
	int w=0;\
	char ch=getchar();\
	while(ch<'0'||ch>'9')\
		ch=='-'&&(w=1),\
		ch=getchar();\
	while(ch>='0'&&ch<='9')\
		x=(x*10)+(ch^48),\
		ch=getchar();\
	w&&(x=-x);\
}

inline void rorate(){
	int d=std::time(0)%400;
	long double z=sin(d/100.0),w=cos(d/100.0);
	for(int i=1;i<=n;i++){
		int x=a[i].x,y=a[i].y;
		a[i].x=x*w-y*z;
		a[i].y=x*z+y*w;
	}
}

inline long double dis(int x,int y){
	return (a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y);
}

int main(){
	read(n);
	for(ri i=1;i<=n;i++){
		read(a[i].x);
		read(a[i].y);
	}
	rorate();
	sort(a+1,a+1+n,cmp);
	long double d=1145141919810114;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=min(60,n-i);j++){
			d=min(d,dis(i,i+j));
		}
	} 
	cout<<fixed<<setprecision(4)<<sqrt((long long)round(d));
	
    return 0;
}

一看最优解榜，一共就 $88$ 页，这代码排第 $10$ 页。

这当然是不行的。考虑优（xuan）化（xue）。
我 ~~（用名字颜色）~~ 注意到，这数据实在是太水，太水，太水了。实测在不旋转的情况下，只需要按 $x$ 坐标排序后，每个点往后判断 $3$ 个点（ACGO的数据甚至只需要判 $2$ 个）就可以 AC。

然后，把我的快读进化成光读，用 register 系列卡亿卡常，再压亿压行，就一举拿下了最短最优解。

压行代码：

#include<stdio.h>
#include<math.h>
#include<algorithm>
#define ri register int
#define rll register long long
#define r(x)w=0;ch=getchar();while(ch<'0'||ch>'9')ch=='-'&&(w=1),ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();w&&(x=-x);
#define dis(c,d)(long long)(a[c].x-a[d].x)*(a[c].x-a[d].x)+(long long)(a[c].y-a[d].y)*(a[c].y-a[d].y)
#define min(x,y)((x)>(y)?(y):(x))
struct p{int x,y;}a[10001];int n;bool w;char ch;bool c(p x,p y){return x.x<y.x;}int main(){r(n);for(ri i=1;i<=n;i++){r(a[i].x);r(a[i].y);}std::sort(a+1,a+1+n,c);rll d=1145141919810114;for(ri i=1;i<=n;i++){ri t=min(3,n-i);for(ri j=1;j<=t;j++){rll tt=dis(i,i+j);d=min(d,tt);}}printf("%.4f",sqrt(round(d)));return 0;}

未压行的：

#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <ctime>
using namespace std;

#define ri register int
#define inf 1000000000000000000

struct pos{
	int x, y;
}a[400005];
int n;
bool cmp(pos x,pos y){return x.x*x.y<y.x*y.y;}

#define read(x) {\
	int w=0;\
	char ch=getchar();\
	while(ch<'0'||ch>'9')\
		ch=='-'&&(w=1),\
		ch=getchar();\
	while(ch>='0'&&ch<='9')\
		x=(x<<3)+(x<<1)+(ch^48),\
		ch=getchar();\
	w&&(x=-x);\
}

#define dis(c,d) (long long)(a[c].x-a[d].x)*(a[c].x-a[d].x)+(long long)(a[c].y-a[d].y)*(a[c].y-a[d].y)

int main(){
	read(n);
	for(ri i=1;i<=n;i++){
		read(a[i].x);
		read(a[i].y);
	}
	sort(a+1,a+1+n,cmp);
	long long d=1145141919810114;
	for(ri i=1;i<=n;i++){
		ri t=min(5,n-i);
		for(ri j=1;j<=t;j++){
			long long tt;
			if((tt=dis(i,i+j))<d)d=tt;
		}
	}
	cout<<fixed<<setprecision(4)<<sqrt(round(d));
	
    return 0;
}

附最优解帅照。

对于那个旋转也许大家不太理解。其实用到了两条公式：

$x'=x\cos\theta-y\sin\theta$
$y'=x\sin\theta+y\cos\theta$

其中 $(x,y)$ 是原来的坐标， $(x',y')$ 是旋转后的坐标， $\theta$ 是旋转角。
这里直接使用 $time \bmod 400$ 来做随机旋转角了。

附赠：
平面最近点对（加强版）（ACGO）
P1429 平面最近点对（加强版）（洛谷）
P7883 平面最近点对（加强加强版）（洛谷）
这三题和本题除了数据和数据范围就只有一些细节不同了。这三题的正解是 $O(n\log n)$ 或 $O(n\log^2 n)$ 的分治，但是这个随机旋转+排序如果能打好，也能 AC。~~建议在交加强加强版之前先去洗个脸（滑稽）。~~

加油哦（

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论