自动搬运

查看原文

来自洛谷，原作者为

	ix35 垒球

搬运于2025-08-24 22:26:16，当前版本为作者最后更新于2021-06-14 15:39:20，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

求出 $chk(i,j)$ 表示是否对所有 $k\in (i,j)$ 都有 $P_k$ 到 $P_iP_j$ 的距离不超过 $d$，随后我们用 $dp(i)$ 表示到达 $i$ 能经过的最少点数然后随便 DP 就可以了。

那么如何求 $chk(i,j)$ 呢？

考虑某个 $k>i$，如果要满足 $P_k$ 到 $P_iP_j$ 距离不超过 $d$，那么：

• 若 $P_kP_i\leq d$，那么没有限制；

• 否则，$P_iP_j$ 与 $P_iP_k$ 的夹角应当不大于 $\arcsin(\dfrac{d}{|P_iP_k|})$。

于是在处理所有 $chk(i,j)$ 时，我们顺次扫描 $k>i$，记录它对 $P_iP_j$ 极角的区间限制，然后对这个 $k$ 计算它是否在 $i+1,\ldots,k-1$ 所划定的区间内即可。

时间复杂度为 $O(n^2)$。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=2010;
const double pi=acos(-1.0),eps=1e-8;
struct P {
	double x,y;
}p[MAXN];
int n,dp[MAXN],trans[MAXN][MAXN];
double d,al,ar,bl,br;
double calcslp (P a,P b) {
	return atan2(b.y-a.y,b.x-a.x);
}
double calcdis (P a,P b) {
	return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
}
pair<double,double> calc (P a,P b) {
	double plragl=calcslp(a,b);
	double delagl=asin(d/calcdis(a,b));
	pair<double,double> res=make_pair(plragl-delagl,plragl+delagl);
	return res;
}
int main () {
	scanf("%d%lf",&n,&d);
	for (int i=1;i<=n;i++) {
		scanf("%lf%lf",&p[i].x,&p[i].y);
		for (int j=i+1;j<=n;j++) {trans[i][j]=1;}
	}
	for (int i=1;i<=n;i++) {
		al=bl=-pi-eps,ar=br=pi+eps;
		for (int j=i+1;j<=n;j++) {
			double tmp=calcslp(p[i],p[j]);
			if ((tmp<al||tmp>ar)&&(tmp<bl||tmp>br)) {trans[i][j]=0;}
			if (calcdis(p[i],p[j])>d) {
				pair<double,double> bd=calc(p[i],p[j]);
				if (bd.first>=-pi-eps&&bd.second<=pi+eps) {
					al=max(al,bd.first),ar=min(ar,bd.second);
					bl=max(bl,bd.first),br=min(br,bd.second);
				} else if (bd.first<-pi-eps) {
					ar=min(ar,bd.second);
					bl=max(bl,bd.first+2*pi);
				} else {
					ar=min(ar,bd.second-2*pi);
					bl=max(bl,bd.first);
				}
			}
		}
	}
	for (int i=n;i>=1;i--) {
		al=bl=-pi-eps,ar=br=pi+eps;
		for (int j=i-1;j>=1;j--) {
			double tmp=calcslp(p[i],p[j]);
			if ((tmp<al||tmp>ar)&&(tmp<bl||tmp>br)) {trans[j][i]=0;}
			if (calcdis(p[i],p[j])>d) {
				pair<double,double> bd=calc(p[i],p[j]);
				if (bd.first>=-pi-eps&&bd.second<=pi+eps) {
					al=max(al,bd.first),ar=min(ar,bd.second);
					bl=max(bl,bd.first),br=min(br,bd.second);
				} else if (bd.first<-pi-eps) {
					ar=min(ar,bd.second);
					bl=max(bl,bd.first+2*pi);
				} else {
					ar=min(ar,bd.second-2*pi);
					bl=max(bl,bd.first);
				}
			}
		}
	}
	memset(dp,0x3f,sizeof(dp));
	dp[1]=1;
	for (int i=2;i<=n;i++) {
		for (int j=1;j<i;j++) {
			if (trans[j][i]) {dp[i]=min(dp[i],dp[j]+1);}
		}
	}
	printf("%d\n",dp[n]);
	return 0;
}