自动搬运

查看原文

来自洛谷，原作者为

	agicy 你很懒，什么都看不到

搬运于2025-08-24 21:57:52，当前版本为作者最后更新于2020-04-20 12:27:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

点此使用更佳 $\huge{\texttt{My Blog}}$。

一道诡异的 计算几何 的题目，光从名字就可以看出来它的诡异。

题目链接：Luogu P4227/LibreOJ 2329/UOJ 344/清华集训2017 D4T1。

题目

题目描述

九条可怜是一个贪玩的女孩子。

这天她在一堵墙钉了 $n$ 个钉子，第 $i$ 个钉子的坐标是 $(x_i,y_i)$。接着她又在墙上钉上了 $m$ 根绳子，绳子的一端是点 $s_i(sx_i,sy_i)$，绳子经过点 $t_i(tx_i,ty_i)$，同时绳子的长度是 $L_i$。其中 $s_i$ 点是粘在墙上的，而另一个端点是可以移动的。初始情况下绳子是紧绷的一条直线段。

接着，对每一根绳子可怜都进行了一次游戏。在第 $i$ 次游戏中，可怜会捏着第 $i$ 根绳子的活动端点进行顺时针移动，移动过程中每时每刻绳子都是紧绷的。

不难发现绳子每时每刻都在以某一个位置为圆心作顺时针的圆周运动。初始情况下圆心是绳子的固定端点 $s$，但是在运动的过程中圆心可能会不断发生变化，如下图所示：

图中左侧红点为钉子所在的点，右侧红点为绳子的固定端点，其他颜色的点为虚拟点，活动端点为紫点；绳子从紫点开始运动，在运行到蓝点时绳子绕上左侧红点的钉子，因此活动端点更换了圆心和半径，继续作顺时针的圆周运动。接着活动端点会运行到绿点，并且接下来活动端点会一直绕左侧钉子不停地做圆周运动。

不难发现绳子的运动是不会停止的，因此可怜在她感觉累了之后就会停下来。但是作为一个好奇心满满的女孩子，可怜决定对每一根绳子计算一下如果绳子无限的运行下去，那么它的圆心会切换多少次（包括初始的圆心）。不难发现这个数值一定是有限的。

这里对游戏过程进行一定程度的假设来简化问题：

1. 活动端点在运动的过程中距离每一个钉子的欧几里得距离始终大于等于 $9\times 10^{-4}$。
2. 钉子的坐标两两不同但可能有多点共线。
3. 钉子的体积以及绳子的体积可以忽略不计。在游戏的过程中每一段绳子之间不会互相影响。
4. 初始情况下绳子距离每一个钉子的最近欧几里得距离大于等于 $9\times 10^{-4}$。
5. 每一根绳子初始粘着的端点不会影响绳子的运动，即绳子不会绕回端点上。

数据范围

变量	取值范围
$n$	$\leq 500$
$m$
$T$	$\leq 10$
所有坐标的绝对值	$\leq 10^4$

时空限制

题目	时间限制	空间限制
Luogu P4227	$6-10\text{s}$	$500\text{MiB}$
LibreOJ 2329	$10\text{s}$	$512\text{MiB}$
UOJ 344
清华集训2017 D4T1

题解

你看到这道题目的第一个词（九条可怜）就应该知道出题人是谁了，然后选择放弃。

本题有两种做法，时间效率差距极大（约 $30$ 倍），不过两种做法并无本质差别，只是最后解决方法不同，下面主要讲思路。

思路

考虑暴力的做法。

首先注意到绳子是顺时针旋转，发现这是一个极角减小的过程（不考虑转完一圈时中间的从 $-\pi\to\pi$ 的突变，这个特殊考虑，下文不特殊介绍）。

关于旋转的操作用极坐标一般更为方便（别跟我说你要用什么 $ax+by$ 变换），设当前绳子正在以点 $A$ 为轴转动，以点 $A$ 为极点，水平方向为极轴，那么我们可以发现一个性质。

绳子仅会被小于等于当前角度的最大极角，极径小于等于绳长而又最大的那个点阻碍到。

就像这张图里的例子：

于是，对于每个点开始，将周围的 $n-1$ 个点，按极角排序，那么可以利用极角的单调性二分得出下一个旋转轴的序号，继而递推下去。这样单次操作的时间复杂度是 $\Theta(n\log_2n+\log_2n)$。

下面考虑优化。

当然，对于已经给定的每个点，它周围的 $n-1$ 个点是始终不变的（题目：每一根绳子初始粘着的端点不会影响绳子的运动，即绳子不会绕回端点上），所以我们可以预处理出这些东西，防止每次生成浪费时间。单次查询的复杂度变为 $\Theta(\log_2n)$，预处理的时间复杂度是 $\Theta(n^2+n^2\log_2n)$。

考虑查询次数，发现每次转折，都会使得绳子长度减小，而绳子长度小于 $1$ 时必然无法转折，因为整点的坐标距离至少为 $1$。实际判断是否无限循环时只要判断当前绳长 $L$ 是否小于等于 到其他点的最小距离即可。

所以最坏的情况是两个距离为 $1$ 的点，绳子在上面反复横跳，当 $L$ 很大时，时间效率会当场爆炸。

但是我们可以发现，绳子在反复横跳的时候，经过的结点编号出现了循环节，所以可以直接优化掉中间过程，期望的转折次数为 $\Theta(\log_2L)$，处理单组数据的时间复杂度为 $\Theta(n+n^2+m(\log_2L+\log_2n))$

下面两种做法开始体现他们的不同。

做法一

来自 https://www.cnblogs.com/xiao-ju-ruo-xjr/p/8058382.html ，好像洛谷上还有一篇题解就是转载这个的。

考虑用预处理的方式优化。我们令 $A(x,y,z)$ 表示轴心在点 $x$，方向指向点 $y$，当长度为 $z$ 的时候恰好可以走到的下一个节点编号。那么预处理的时候我们先枚举点 $x$，然后以 $x$ 为原点极角排序，接下来一遍 $\Theta(n^2)$ 就可以搞定了。那么在询问时只需要二分一下极角，然后再二分一下长度，就可以在 $\Theta(\log_2n)$ 的时间内找到下一个点了。

大家可以自己去看代码，真的是写得让人感到生命已如风中残烛，并且比较容易出错，大家谨慎阅读。（别问我为什么知道，因为我也是这么写的）

这种做法将长度单调递增时的每一个阶段都划分开来，空间复杂度为 $\Theta(n^3)$，最坏时间复杂度为 $n^3$，肯定会被卡，并且预处理和查询的效率及其低下，代码还比较长，不推荐。

做法二

改进预处理，保存每个点的周围点的数据（极角、极径、下一个点的编号），并以极角为第一关键字，极径为第二关键字排序（$\Theta(n^2+n^2\log_2n)$）。

将查询时的二分改进一下，排序时加入。直接对角度进行二分，画图可知，转折点排序后距离二分结果点应该不远，且大部分编号都小于二分结果，最坏的结果是要遍历完 $n$ 个点，但是根据玄学的势能分析法可以得出单次查询的复杂度为 $\Theta(\log_2n)$。

此外，上一种做法判断循环节时经常初始化大数组，时间复杂度为 $\Theta(Tmn^2)$，其实直接用 int 标记（第几次查询时是否经过）代替 bool 标记（当前查询是否经过）即节省初始化数组的时间。

代码

显然是第二种做法的代码。

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define INF 1e9 //定义正无穷
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg bool f=false;
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return f?-res:res;
}

const long double eps=1e-8; //eps 判定浮点数用

inline int sgn(reg double x){ //符号函数
	if(fabs(x)<eps)
		return 0;
	else if(x>0)
		return 1;
	else
		return -1;
}

const int MAXN=500+5; //数据范围

inline void Read(void);
inline void Work(void);

int main(void){
	reg int T=read();
	while(T--){
		Read();
		Work();
	}
	return 0;
}

struct Node{
	int x,y;
	inline void Read(void){
		x=read(),y=read();
		return;
	}
};

inline double GetDis(const Node& a,const Node& b){ //坐标差值的乘积不会爆 int，不用强制转换
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

inline double GetAng(const Node& a,const Node& b){ //求极角
	return atan2(b.y-a.y,b.x-a.x);
}

int n,m;
Node nail[MAXN]; //钉子

inline void Read(void){ //读入函数
	n=read(),m=read();
	for(reg int i=1;i<=n;++i)
		nail[i].Read();
	return;
}

struct Edge{
	double angle,length; //angle 表示极角，length 表示极径
	int to; //to 表示编号
	inline Edge(reg double angle=0,reg double length=0,reg int to=0):angle(angle),length(length),to(to){
		return;
	}
	inline bool operator<(const Edge& a)const{ //排序
		return sgn(angle-a.angle)==0?sgn(length-a.length)<0:sgn(angle-a.angle)<0;
	}
};

double Min[MAXN]; //Min[i] 表示点 i 到其他点的最小距离是 Min[i]
Edge C[MAXN][MAXN];

int tim,vis[MAXN][MAXN]; //tim 是表示当前是第几次查询，vis[i][j] 表示最近一次从 i 到 j 的转折发生在 vis[i][j] 次查询
int Las[MAXN][MAXN]; //上一次答案（求循环节长度）
long double His[MAXN][MAXN]; //中途经过的路程

inline void Solve(reg double angle,reg long double L){
	++tim;
	angle-=eps; //可能会有等于的情况出现
	reg int ans=1,now=0;
	while(sgn(L-Min[now])>=0){
		reg int cnt=(now==0)?n:n-1; //其他点的数量
		reg int l=1,r=cnt,res=-1;
		while(l<=r){ //二分求结果
			reg int mid=(l+r)>>1;
			if(sgn(C[now][mid].angle-angle)>=0){
				res=mid;
				r=mid-1;
			}
			else
				l=mid+1;
		}
		if(res==-1)
			res=cnt;
		else
			res=(res+cnt-2)%cnt+1;
		reg int t=res;
		while(sgn(L-C[now][t].length)<0)
			t=(t+cnt-2)%cnt+1; //如果不行就向前枚举
		L-=C[now][t].length; //长度减少
		angle=C[now][t].angle; //角度更新
		reg int nxt=C[now][t].to; //下一个点的编号
		if(vis[now][nxt]==tim){ //出现循环
			reg long double delta=His[now][nxt]-L; //循环节的路程长度
			reg int cycle=floor(L/delta); //循环多少次
			ans+=cycle*(ans-Las[now][nxt]+1); //循环节长度
			L-=cycle*delta; //长度减少
		}
		++ans; //统计答案
		vis[now][nxt]=tim;
		Las[now][nxt]=ans;
		His[now][nxt]=L;
		now=nxt; //更新信息
	}
	printf("%d\n",ans); //输出答案
	return;
}

inline void Work(void){
	for(reg int i=1;i<=n;++i){
		reg int cnt=0;
		Min[i]=INF; //初始化
		for(reg int j=1;j<=n;++j)
			if(i!=j){
				double Dis=GetDis(nail[i],nail[j]);
				C[i][++cnt]=Edge(GetAng(nail[i],nail[j]),Dis,j);
				Min[i]=min(Min[i],Dis);
			}
		sort(C[i]+1,C[i]+cnt+1); //排序
	}
	while(m--){
		static int L;
		static Node s,t;
		s.Read(),t.Read(),L=read();
		nail[0]=s; //起点放在 [0] 上
		Min[0]=INF; //初始化
		for(reg int i=1;i<=n;++i){
			double Dis=GetDis(nail[0],nail[i]);
			C[0][i]=Edge(GetAng(nail[0],nail[i]),Dis,i);
			Min[0]=min(Min[0],Dis);
		}
		sort(C[0]+1,C[0]+n+1); //排序
		Solve(GetAng(s,t),L);
	}
	return;
}