欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces 385D -Bear and Floodlight (状压DP+几何)

程序员文章站 2022-07-03 21:47:01
...

D. Bear and Floodlight
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

One day a bear lived on the Oxy axis. He was afraid of the dark, so he couldn't move at night along the plane points that aren't lit. One day the bear wanted to have a night walk from his house at point (l, 0) to his friend's house at point (r, 0), along the segment of length(r - l). Of course, if he wants to make this walk, he needs each point of the segment to be lit. That's why the bear called his friend (and yes, in the middle of the night) asking for a very delicate favor.

The Oxy axis contains n floodlights. Floodlight i is at point (xi, yi) and can light any angle of the plane as large as ai degree with vertex at point (xi, yi). The bear asked his friend to turn the floodlights so that he (the bear) could go as far away from his house as possible during the walking along the segment. His kind friend agreed to fulfill his request. And while he is at it, the bear wonders: what is the furthest he can go away from his house? Hep him and find this distance.

Consider that the plane has no obstacles and no other light sources besides the floodlights. The bear's friend cannot turn the floodlights during the bear's walk. Assume that after all the floodlights are turned in the correct direction, the bear goes for a walk and his friend goes to bed.

Input

The first line contains three space-separated integers nlr (1 ≤ n ≤ 20;  - 105 ≤ l ≤ r ≤ 105). The i-th of the next n lines contain three space-separated integers xiyiai ( - 1000 ≤ xi ≤ 1000; 1 ≤ yi ≤ 1000; 1 ≤ ai ≤ 90) — the floodlights' description.

Note that two floodlights can be at the same point of the plane.

Output

Print a single real number — the answer to the problem. The answer will be considered correct if its relative or absolute error doesn't exceed 10 - 6.

Examples
input
2 3 5
3 1 45
5 1 45
output
2.000000000
input
1 0 1
1 1 30
output
0.732050808
input
1 0 1
1 1 45
output
1.000000000
input
1 0 2
0 2 90
output
2.000000000
Note

In the first sample, one of the possible solutions is:

Codeforces 385D -Bear and Floodlight (状压DP+几何)

In the second sample, a single solution is:

Codeforces 385D -Bear and Floodlight (状压DP+几何)

In the third sample, a single solution is:

Codeforces 385D -Bear and Floodlight (状压DP+几何)


题意:

二维平面上有n个探照灯,第i个灯在(xi,yi)出,且可以照亮任意a[i]度角的范围,问这n个灯最多可照亮x轴上区间[l,r]区域从l开始被照亮的连续的最长长度 
Input 
第一行三个整数n,l,r表示灯的数量和要照亮的范围,之后n行每行三个整数xi,yi,ai分别表示第i个灯的二维坐标和照亮的范围(1<=n<=20,-1e5<=l<=r<=1e5,-1000<=xi<=1000,1<=yi<=1000,1<=ai<=90) 
Output 
输出[l,r]区域从l开始被照亮的连续的最长长度 
Sample Input 
2 3 5 
3 1 45 
5 1 45 
Sample Output 
2.000000000 
Solution 

状压DP,一个状态i表示亮灯的集合,i的二进制表示中第j位是1表示第j个灯亮,否则不亮,dp[i]表示i状态最多可以照亮的连续区域长度,转移方程为dp[i&(1 << j)]=max(dp[i&(1 << j)],dp[i]+deal(dp[i],j)),其中i&(1 << j)=0表示第j个灯不在i状态中然后把第j个灯的照射范围放在最右边,deal(dp[i],j)求出第j个灯从dp[i]位置开始照可以照多长的距离,最终dp[(1 << n)-1]即为答案。刚开始看真的令人窒息。不过想到状压DP就好写了。

代码:

#include<bits/stdc++.h>
using namespace std;
const int  MAX_N = 1<<20;
const int MOD = 1e9+7;
double dp[MAX_N];
double x[25],y[25],a[25],l,r;
double solve(double len,int j)
{
    double temp = atan((r-x[j])/y[j]);
    temp = min(temp,atan((len-x[j])/y[j])+a[j]);
    return x[j] + (y[j] * tan(temp));
}

int main()
{
    int N,M,T;
    while(~scanf("%d%lf%lf",&N,&l,&r))
    {
        r -= l;
        memset(dp,0,sizeof(dp));
        for(int i=0;i<N;i++)
        {
            scanf("%lf%lf%lf",&x[i],&y[i],&a[i]);
            x[i] -= l;
            a[i]=a[i]/180.*acos(-1.0); //atan中变量为弧度
            cout<<a[i]<<endl;
        }
        int n = 1<<N;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<N;j++)
            {
                if((i&(1<<j))==0)
                {
                    dp[i^(1<<j)] = max(dp[i^(1<<j)] ,solve(dp[i],j));
                }
            }
        }
        printf("%.12f\n",dp[n-1]);
    }
    return 0;
}