CF385D Bear and Floodlight

题意简述（翻译）

在平面直角坐标系上，沿直线从 $(l,0)$ 走到 $(r,0)$ 。有 $n$ 盏灯，第 $i$ 盏灯位于 $(x_i,y_i)$ ，可以照亮的角度为 $a_i°$ （注意不是弧度制）。途中不能经过未照亮的区域，求能走的最远距离。

正解

注意到 $n\le 20$ ，明显是状压DP。

为方便计算，纵坐标 $y_i$ 取绝对值，不影响正确性。

考虑加入一盏灯 $A(x_i,y_i)$ ，令始边过 $(f[s],0)$ 是最优的。

当 $x_i$ 大于 $f[s]$ 时，画个图，分类讨论，运用一些三角函数知识进行计算（比较基础，详见代码和下图）；不大于时同理，但还要考虑到这盏灯可以照亮 $(f[s],+\infty )$ 的情况。

$x_i>f[s]$的第一种情况

$x_i>f[s]$的第二种情况

$x_i\le f[s]$的第一种情况

$x_i\le f[s]$的第二种情况

#include
#define mid ((l+r)>>1)
#define inf 1000000007
#define ldb long double
#define hehe pair<pair<ldb,ldb>,ldb>
#define fir first
#define sec second
#define pi (ldb)(3.14159265358979)
#define N 25
#define M ((1<<20)+5)
using namespace std;
long long read()
{
	long long x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<1ll)+(x<<3ll)+ch-48,ch=getchar();
	return x*f;
}
void write(long long x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
int n,m;
ldb f[M],l,r;
hehe a[N];
ldb rad(ldb alpha)
{
	return alpha/(ldb)180*pi;
}
int main()
{
	n=read(),l=read(),r=read();
	for(int i=0;i<n;i++)
	{
		ldb x=read(),y=read(),z=read();
		a[i]={{x,fabs(y)},rad(z)};
	}
	for(int s=0;s<(1<<n);s++)f[s]=l;
	for(int s=0;s<(1<<n);s++)
	{
		for(int i=0;i<n;i++)
		{
			if((s>>i)&1)continue;
			ldb x=(a[i].fir).fir,y=(a[i].fir).sec,alpha=a[i].sec,beta,theta;
			int ss=s|(1<<i);
			if(x>f[s])
			{
				beta=atan((x-f[s])/y);
				if(alpha>beta)
				{
					theta=alpha-beta;
					f[ss]=max(x+y*tan(theta),f[ss]);
					f[ss]=min(f[ss],r);
				}
				else
				{
					theta=beta-alpha;
					f[ss]=max(x-y*tan(theta),f[ss]);
					f[ss]=min(f[ss],r);
				}
			}
			else
			{
				beta=atan((f[s]-x)/y);
				theta=alpha+beta;
				if(theta>rad(90))f[ss]=r;
				else f[ss]=max(x+y*tan(theta),f[ss]);
				f[ss]=min(f[ss],r);
			}
		}
	}
	printf("%.8Lf\n",f[(1<<n)-1]-l);
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77