Codeforces 385(#226 Div2 only) D. Bear and Floodlight

問題

数直線上y = 0の線を、x = lからx = rまで移動したい。
n個のライトがあって、それぞれの座標は(x[i], y[i])で、
a[i]度の角度の範囲だけを照らすことができる。

移動できる部分は、線分に一つ以上のライトがかかっているところだけ。
最大でどれだけ移動できるか求めよ。

制約条件

n≦20
y[i]は1以上

方針

ビットDP.
dp[bit]をbitのライトを使ったときにいける最も右の位置とする。

位置と次に試すライトを決めたら、その位置がギリギリ入るようにライトを向ければいいので、次の右端がわかる。
これで更新をしていけばばいい。

ライトの範囲がrを超えてしまう場合があるのでrまでにする。

ソースコード

typedef complex<double> P;
int n, l, r;
P p[20];
double a[20];
double dp[1 << 20];

int main(){
	
	cin >> n >> l >> r;
	rep(i, n){
		cin >> p[i].real() >> p[i].imag() >> a[i];
		a[i] *= PI / 180;
	}
	
	rep(i, 1 << n) dp[i] = -INF;
	dp[0] = l;
	
	rep(i, 1 << n) if(dp[i] > -INF) rep(j, n) if(!(i & 1 << j)){
		
		P d = P(dp[i], 0) - p[j];
		
		double ang = arg((P(r, 0) - p[j]) / d);
		ang = min(ang, a[j]);
		
		d *= P(cos(ang), sin(ang));
		d *= -p[j].imag() / d.imag();
		
		dp[i ^ 1 << j] = max(dp[i ^ 1 << j], p[j].real() + d.real());
	}
	cout << setprecision(20) << fixed << 
	dp[(1 << n) - 1] - l << endl;
	
	return 0;
}