[NWRRC2015]Kingdom Trip 题解

ix35 · 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;
}