题解：CF385D Bear and Floodlight

__vector__ · 2025-09-12 16:40:31 · 题解

考虑到对于已经选择的灯的集合，调整顺序使得能走的距离更远总是不劣的，可以反证法证明。

令 f_{s} 表示已经使用了 s 集合的灯，此时能走的最远距离。

转移的话，就枚举一个新的未使用的灯。

此时，新的灯的照亮的左边界必然就是 f_s，现在需要算出这盏灯照亮的右边界。

此时，已经知道了灯的位置 (x_1,y_1)，以及灯光覆盖的左边界 (k_1,0)，现在要求出灯光覆盖的右边界 (k_2,0)。

现在可以先求出 (x_1,y_1) 指向 (k_1,0) 的极角（极轴为 x 轴正向），可以调用 C++ 函数 atan2(0-y,k-x1) 得到。

随后将这个角度加上 \alpha 就能得到 (x_1,y_1) 指向 (k_2,0) 的极角，令其为 \theta。

此时考虑构造一个以 (x_1,y_1) 为中心的单位圆，算出其与穿过 (x_1,y_1) 和 (k_2,0) 的直线的交点的横纵坐标相对于 (x_1,y_1) 为 (sin(\theta),cos(\theta)) 。

那么可以得到穿过 (x_1,y_1) 和 (k_2,0) 的直线的斜率是 \frac{\sin(\theta)}{\cos(\theta)} = \tan(\theta)。

那么现在可以得到：

上述式子成功求出了灯光覆盖的右边界，需要注意若 \theta \ge 0，那么右边会延伸到无穷远，因为此时灯光覆盖区域大概长这个样子：

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
void ioopti(){
    ios::sync_with_stdio(0);
    cin.tie(0);
}
typedef long double ld;
const ld pi=acos(ld(-1));
ld turn(ld jiaodu){
    return jiaodu*(pi/ld(180));
}
ld calc(pair<ld,ld> nd,ld deg,ld fir){
    ld xcha=nd.fi-fir;
    ld ycha=nd.se;
    ld len=hypot(xcha,ycha);
    xcha/=len,ycha/=len;
    ld curdeg=atan2(-ycha,-xcha);
    curdeg+=turn(deg);
    ld dx=cos(curdeg),dy=sin(curdeg);
//    printf("dx %.10Lf dy %.10Lf\n",dx,dy);
    if(abs(dy)<1e-10){
        if(dx>0)return 1e300;
        return fir;
    }
    if(dy>0){
        return 1e300;
    }
    return max(nd.fi+dx*(nd.se/(-dy)),fir);
}
const int maxn=25;
int n;
ld l,r;
pair<ld,ld> nd[maxn];
ld a[maxn];
ld f[1<<21];
void solve(int id_of_test){
    scanf("%d%Lf%Lf",&n,&l,&r);
    FOR(i,1,n){
        scanf("%Lf%Lf%Lf",&nd[i].fi,&nd[i].se,&a[i]);
    }
    int all=(1<<n)-1;
    FOR(msk,0,all){
        f[msk]=-1e18;
    }
//    printf("calc = %.10Lf\n",calc(nd[1],a[1],0.00001));
    f[0]=l;
    FOR(msk,0,all){
        if(f[msk]<-1e10)continue;
        FOR(i,1,n){
            if(!(msk&(1<<(i-1)))){
                ckmx(f[msk|(1<<(i-1))],calc(nd[i],a[i],f[msk]));
            }
        }
      //  printf("f[%d] = %.10Lf\n",msk,f[msk]);
    }
    printf("%.9Lf\n",min(f[all],r)-l);
}
int main()
{
    int T;
    T=1;
    FOR(_,1,T){
        solve(_);
    }
    return 0;
}
/*
1. 对题意的理解能否和样例对的上？  
2. 每一步操作，能否和自己的想法对应上？  
3. 每一步操作的正确性是否有保证？  
4. 是否考虑到了所有的 case？特别是极限数据。
5. 变量的数据类型是否与其值域匹配？
6. 时间复杂度有保证吗？
7. 空间多少 MB？  
*/