Rest In The Shades

发表于

题面

  
平面上有一个点光源, 以每秒一个单位的速度从 $(x_0, y)$ 沿直线走到 $(x_1, y)$, $y < 0$,
$x$ 轴上有 $n$ 条线段会遮挡光线, $x$ 轴上方有 $q$ 个点, 你需要计算出每个点能够被光线直射的总时间.

  
$n, q \le 10^5$

题解

此题看似复杂，实际上也有迹可循
  
首先每一个点被照射的时间就是从这个点投影在光源的轨迹上的总长度（即将被照射的的点看作点光源）,
由于光源的轨迹与 $x$ 轴是平行的, 所以在轨迹上的长度和在 $x$ 轴上的长度比值是定值,
只要计算在 $x$ 轴上投影的距离即可.

  
先求出到光源的轨迹两端点的连线与 $x$ 轴的交点然后二分左右端点即可, 两端的多出部分需要特殊考虑一下.

标程

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
#include<cstdio>
#include<algorithm>
#define N (2e5+5)
#define INF 1000000000
#define eps (1e-9)

using namespace std;

double sy,a,b,sum[N],l[N],r[N];
int n,q;

inline void solve()
{
    scanf("%d",&q); 
    for (int i=1;i<=q;i++)
    {
        double x,y;
        scanf("%lf%lf",&x,&y);
        double sfb=y/(y-sy);
        double pax=a-x,pbx=b-x;
        pax*=sfb; pbx*=sfb;
        pax+=x; pbx+=x;
        if (pbx<=l[1])
        {
            printf("0.00000000\n");
            continue;
        }
        if (pax>=r[n])
        {
            printf("0.00000000\n");
            continue;
        }
        double ans=0;
        int L=1,R=n; 
        while (L<R)
        {
            int mid=(L+R+1)>>1;
            if (l[mid]<=pax) L=mid;
                else R=mid-1;
        }
        ans-=sum[L]-max(0.0,r[L]-pax);
        L=1,R=n;
        while (L<R)
        {
            int mid=(L+R)>>1;
            if (r[mid]>=pbx) R=mid;
                else L=mid+1;
        }
        ans+=sum[R];
        ans-=min(r[L]-pbx,r[L]-l[L]);
        ans=ans*(b-a)/(pbx-pax); 
        printf("%.7lf\n",ans);
    }
}
int main()
{
    scanf("%lf%lf%lf",&sy,&a,&b);
    scanf("%d",&n); n++;
    l[1]=r[1]=0; 
    for (int i=2;i<=n;i++)
    {
        scanf("%lf%lf",&l[i],&r[i]);
        sum[i]=sum[i-1]+(r[i]-l[i]);
    }
    l[++n]=r[n]=INF;
    sum[n]=sum[n-1];
    solve();
    return 0;
}