【Codeforces 1167G】Low Budget Inception | Mrsrz's blog

计算几何，双指针。

题目大意：

在数轴上有 $n$ 个物体，每个物体是 $1\times 1$ 的矩形。物体的左下、右下顶点都在数轴的整点上，且没有重合。保证两个物体的距离不超过 $d$。

现在给定 $m$ 个询问，每个询问给出一个位置 $x$，问以 $x$ 为顶点，将数轴向内翻折，直到有物体和另一个物体或者数轴接触为止。问形成的夹角的弧度是多少。

题解：

考虑两种不同的相撞方式：

1. 物体和数轴相撞。我们只需要考虑 $x$ 左右最近的两个物体和数轴相撞即可。假设最近的物体距离其为 $s$，则夹角的度数就是 $\arctan\frac 1 s$。
2. 物体和物体相撞。不难发现，两个物体分别在 $x$ 左边和右边，且到 $x$ 的距离为 $a$ 和 $b$，那么当且仅当 $|a-b|\leq 1$ 的时候，这两个物体相撞。夹角的度数就是 $2\arctan\frac 1 {\max(a,b)}$。

对于情况 1，我们直接二分得到离它最近的两个位置即可。

对于情况 2，我们只要找一组最小的 $a,b$ 即可，更大的相撞的夹角显然会小。

我们用双指针枚举左边、右边的物体，每次把距离 $x$ 近的那个指针向外移动即可。如果有一个指针距离 $x$ 超过 $d$ 了，那么答案一定不会比情况 1 优，此时可以直接退出。

对所有情况求出的夹角取 $\max$ 即可。

时间复杂度 $O(n+m\log n+md)$。

瓶颈主要在情况 2 的双指针部分。但是由于这个双指针没法卡满，而且询问的 $x$ 是互不相同的，所以常数较小，暴力可以在 $3$ 秒内通过。

可以使用 bitset 进行优化。

Code：

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=200005;
int n,d,a[N],m;
int main(){
    scanf("%d%d",&n,&d);
    for(int i=1;i<=n;++i)scanf("%d",a+i),++a[i],a[0]=-0x3fffffff,a[n+1]=0x7fffffff;
    for(scanf("%d",&m);m--;){
        double ans=0;
        int x;
        scanf("%d",&x);
        int pos=lower_bound(a+1,a+n+1,x+1)-a-1;
        ans=max(ans,atan(1./(x-a[pos])));
        if(pos!=n)ans=max(ans,atan(1./(a[pos+1]-1-x)));
        int l=pos,r=pos+1;
        while(x-a[l]<=d&&a[r]-1-x<=d&&abs(a[r]-1-x-x+a[l])>1)
        x-a[l]<=a[r]-1-x?--l:++r;
        if(abs(a[r]-1-x-x+a[l])<=1){
            int k=max(a[r]-1-x,x-a[l]);
            ans=max(ans,2*atan(1./k));
        }
        printf("%.14f\n",ans);
    }
    return 0;
}