Codeforces ECR #065 : G. Low Budget Inception

一見ややこしそうで意外に難しくない問題。
https://codeforces.com/contest/1167/problem/G

問題

直線上に、1辺1の正方形がいくつか並んでいる。
直線上の１点を指定し、その右側を左回りに回転させよう。

指定した点の左側と接するまで、右側の回転を進める。
その時、直線を折り曲げた箇所の成す角度を求めよ。

解法

左側と右側の矩形がぶつからないケースは簡単である。
折り曲げた点の左側にある最寄の正方形が折り曲げた直線とぶつかるケースと、逆に右側にある最寄りの正方形と左側の直線がぶつかるケースを求め大きい方の角度を取ろう。

残りは、両方の正方形がぶつかるケースである。
折り曲げた点から左右にある正方形を尺取り法の要領で見ていき、互いにぶつかるケースを求めよう。
正方形間の距離(d)が短いため、上のケース（正方形と直線がぶつかるケース）の角度がそれなりに大きいので、探索すべき正方形の数はさほど大きくないためO(Nd)で処理が終わり間に合う。

int N,D;
ll A[202020];
int M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>D;
	FOR(i,N) cin>>A[i];
	
	cin>>M;
	FOR(i,M) {
		cin>>x;
		
		if(x==A[0] || x==A[N-1]+1) {
			_P("%.12lf\n",atan(1)*2);
			continue;
		}
		
		y=lower_bound(A,A+N,x)-A;
		
		if(A[y]==x && A[y-1]==x-1) {
			_P("%.12lf\n",atan(1)*4);
			continue;
		}
		if(A[y]==x || A[y-1]==x-1) {
			_P("%.12lf\n",atan(1)*2);
			continue;
		}
		
		ll dif=min(x-A[y-1]-1,A[y]-x);
		double ret=atan(1.0/dif);
		int L=y-1;
		int R=y;
		
		int ok=0;
		for(j=20;j>=0;j--) if(2*atan(1.0/(ok+(1<<j)))>=ret) ok+=1<<j;
		
		while(L>=0 && R<N) {
			int dl=x-(A[L]+1);
			int dr=A[R]-x;
			
			if(max(dl,dr)>ok) break;
			
			if(abs(dl-dr)<=1) {
				ret=2*atan(1.0/max(dl,dr));
				break;
			}
			if(dl<dr) L--;
			else R++;
		}
		
		_P("%.12lf\n",ret);
	}
}

まとめ

ECRのGの割には軽い。