Link.
Description.
有很多个房子，都是单位正方形，左下角为 \((x_i,0)\)，右上角为 \((x_i+1,1)\)。
保证 \(x_i\in\mathbb N\)，房子不相交，相邻两个房子距离不超过 \(D\)。
现在有若干个点，问以这若干个点为中心旋转数轴，使得房子不相交、房子不与地面相交。
能旋转的角度是多少，\(m\) 次询问。
\(n,m\le 2\times 10^5,D\le 7000\)
Solution.
有两种情况
- 某个房子撞到了数轴上
- 某两个房子互相撞到了
由于所有房子坐标都是整数，所以 2 情况要求 \(|x+y-2w|\le 1\)。
其中 \(w\) 是查询位置。
画张图，发现肯定有 \(\vartheta=2\text{atan}(\frac 1{\min(|x-w|,|y-w|)})\)。
情况 1 肯定有 \(\vartheta=\text{atan}(\frac1{|x-w|})\)。
最后肯定是情况 1 2 的最大值。
首先情况 1 可以通过 \(O(1)\) 的双指针求出。
此时如果情况 \(2\) 要大于情况 \(1\)，必须保证 \(\min(|x-w|,|y-w|)\le 2|x-w|\)。
这个结合 \(\text{atan}\) 的性质就可以推出。
那也就是说范围不会很大，只可能在 \([x-2d,x+2d]\) 的范围内。
直接暴扫，复杂度是 \(O(Dm+n)\)，勉强能卡过。
注意这里有一个 Tips：atan2 函数很慢，用他来剪枝不如不用。
更优美一点的方法就是用一个 bitset 维护前 \(2d\) 位。
每次指针移动可以直接通过左移、右移操作求出，每次也就会插入 \(O(1)\) 个点。
然后复杂度就变成了 \(O(\frac D{\omega}m+n)\) 很优美。
Coding.
点击查看代码
//Coded by leapfrog on 2021.10.27 {{{
//是啊，你就是那只鬼了，所以被你碰到以后，就轮到我变成鬼了
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
x=0;char c=getchar(),f=0;
for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1;
for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
f?x=-x:x;
}
template<typename T,typename...L>inline void read(T &x,L&...l) {read(x),read(l...);}//}}}
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
const int N=200005;const double Pi=acos(-1);
int n,D,a[N],m,pos=0;
int main()
{
read(n,D);for(int i=1;i<=n;i++) read(a[i]);
read(m);for(int i=1,x;i<=m;i++)
{
read(x);while(pos<n&&a[pos+1]<x) pos++;
if(a[pos]==x-1&&a[pos+1]==x) {printf("%.15lf\n",Pi);continue;}
if(a[pos]==x-1||a[pos+1]==x) {printf("%.15lf\n",Pi/2);continue;}
int lim=(min(a[pos+1]-x,x-a[pos]-1)+5)*4,pl=pos,pr=pos+1;double rs=0;
if(pos) rs=max(rs,atan2(1.0,x-a[pos]-1));
if(pos!=n) rs=max(rs,atan2(1.0,a[pos+1]-x));
while(pr<=n&&pl>=1&&a[pr]-a[pl]<=lim)
{
int d1=a[pr]-x,d2=x-a[pl]-1;
if(abs(d1-d2)<=1) {rs=max(rs,atan2(1.0,max(d1,d2))*2);break;}
if(d1<d2) pr++;else pl--;
}printf("%.15lf\n",rs);
}return 0;
}