题目概述

有一个光源按照 $(a\to b,s_y)$ 移动，还有 $n$ 个板 $(l_i,r_i)$ 。有 $q$ 个询问，问一个点 $(x,y)$ 被板挡住的总长度。

解题报告

斯波题，但是我不会，被翰爷秒掉。

如果把 $(x,y)$ 当成光源射向板，那么 $y=s_y$ 上被覆盖的区间就是看不见 $(x,y)$ 的区间。

被覆盖的区间有好多，如果第 $i$ 个板产生的区间完全在 $(a,b)$ 内，那么可以通过相似计算出长度为 $(r_i-l_i)(y+s_y)\over y$ 。

二分找出完全在 $(a,b)$ 内的区间，然后边上两个不完全在的特殊处理一下。

我写丑了，WA了若干若干若干若干发。

示例程序

#include<cstdio>
#include<cmath>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long double DB;
const int maxn=200000;

DB Y,A,B;int n,te;pair<DB,DB> s[maxn+5];DB sum[maxn+5];

inline void readf(DB &x) {int now;scanf("%d",&now);x=now;}
inline int fcmp(const DB &a,const DB &b) {if (fabs(a-b)<1e-6) return 0;return a<b?-1:1;}
inline DB getpos(DB x,DB y,DB pos) {DB k=(x-pos)/y;return pos-Y*k;}
inline int FindL(DB x,DB y,int L=1,int R=n){
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        fcmp(A,getpos(x,y,s[mid].fr))<=0?R=mid-1:L=mid+1;return L;
}
inline int FindR(DB x,DB y,int L=1,int R=n){
    for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1))
        fcmp(getpos(x,y,s[mid].sc),B)<=0?L=mid+1:R=mid-1;return R;
}
int main(){
    freopen("E.in","r",stdin);freopen("E.out","w",stdout);
    readf(Y);Y=-Y;readf(A);readf(B);scanf("%d",&n);
    for (int i=1;i<=n;i++) readf(s[i].fr),readf(s[i].sc),sum[i]=sum[i-1]+s[i].sc-s[i].fr;
    for (scanf("%d",&te);te;te--){
        DB x,y;readf(x);readf(y);int L=FindL(x,y),R=FindR(x,y);if (L>R+1) {printf("%.15f\n",double(B-A));continue;}
        if (L>R) {printf("%.15f\n",double(B-A-(L<=n?min(B,getpos(x,y,s[L].fr)):B)+(R?max(A,getpos(x,y,s[R].sc)):A)));continue;}
        DB ans=(sum[R]-sum[L-1])/y*(y+Y);
        if (L>1&&fcmp(A,getpos(x,y,s[L-1].sc))<=0) ans+=getpos(x,y,s[L-1].sc)-A;
        if (R<n&&fcmp(getpos(x,y,s[R+1].fr),B)<=0) ans+=B-getpos(x,y,s[R+1].fr);
        printf("%.15f\n",double(ans));
    }return 0;
}