T<=100, n<=104
比较好想的是把导轨和挡板经过坐标变换让导轨变成X轴（平移+旋转），然后就是一个投影问题。 但是毒瘤的是要求的是挡板长度，所以不同的线段投到X轴上的单位长度的贡献是不一样的，斜率越大单位投影长度的挡板长度越大。 把挡板的端点看做事件点，我们需要知道两个事件点之间的X轴距离以及这段距离单位长度的贡献。 所以需要维护出到某个事件点后离X轴最近的（X轴上方和下方各一个）挡板的贡献。 用扫描线扫过挡板，遇到左端点就插入set中，遇到右端点就删除。 由于挡板不会相交，所以用set计算某个点的y值比较绝对值就可以得到最近的挡板，计算点可以就取当前事件点。 最后的发射器一定紧贴某个事件点，所以可以枚举紧贴左端点，然后右指针移动，过程中累加整段线段，再加上末尾的散段；然后枚举右端点再做一遍即可。 总复杂度 O ( n l o g n ) O(nlogn) O(nlogn)
出题人本来想卡旋转坐标轴的精度，然而开了long double没有人被卡。。 于是我就写了一发旋转坐标轴。
Code：
#include<bits/stdc++.h> #define maxn 10005 #define X first #define Y second using namespace std; typedef long double LD; int T,n,op[maxn<<1]; LD X0,Y0,X1,Y1,len,C,S,ans,Px,pos[maxn<<1],val[maxn<<1]; void rot(LD &x,LD &y){ LD xx=x-X0,yy=y-Y0; x=xx*C+yy*S,y=yy*C-xx*S; } inline LD sqr(LD x){return x*x;} struct Point{ LD x[2],y[2],k,sec; bool operator < (const Point &p)const{return x[0]<p.x[0];} LD calc(){return abs(k*(Px-x[0])+y[0]);} }a[maxn]; bool cmp(int i,int j){return (i>0?a[i].x[0]:a[-i].x[1])<(j>0?a[j].x[0]:a[-j].x[1]);} struct node{int o;bool operator < (const node &B)const{return a[o].calc()<a[B.o].calc();}}; set<node>su,sd; void solve(){ LD ret=0; for(int l=1,r=2;l<2*n;l++){ while(r<=2*n&&pos[r]-pos[l]<len) ret+=val[r-1]*(pos[r]-pos[r-1]),r++; ans=max(ans,ret+(r<=2*n?val[r-1]*(pos[l]+len-pos[r-1]):0)); ret-=val[l]*(pos[l+1]-pos[l]); } } int main() { scanf("%d",&T); while(T--){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%Lf%Lf%Lf%Lf",&a[i].x[0],&a[i].y[0],&a[i].x[1],&a[i].y[1]); scanf("%Lf%Lf%Lf%Lf%Lf",&X0,&Y0,&X1,&Y1,&len); C=(X1-X0)/sqrt(sqr(X1-X0)+sqr(Y1-Y0)),S=(Y1-Y0)/sqrt(sqr(X1-X0)+sqr(Y1-Y0)); for(int i=1;i<=n;i++){ for(int j=0;j<2;j++) rot(a[i].x[j],a[i].y[j]); if(a[i].x[0]>a[i].x[1]) swap(a[i].x[0],a[i].x[1]),swap(a[i].y[0],a[i].y[1]); a[i].k=(a[i].y[1]-a[i].y[0])/(a[i].x[1]-a[i].x[0]); a[i].sec=sqrt(sqr(a[i].x[1]-a[i].x[0])+sqr(a[i].y[1]-a[i].y[0]))/(a[i].x[1]-a[i].x[0]); } for(int i=1;i<=n;i++) op[i]=i,op[n+i]=-i; sort(op+1,op+1+2*n,cmp); for(int i=1,o;i<=2*n;i++){ if(op[i]>0) o=op[i],Px=pos[i]=a[o].x[0],(a[o].y[0]>0?su:sd).insert((node){o}); else o=-op[i],Px=pos[i]=a[o].x[1],(a[o].y[0]>0?su:sd).erase((node){o}); val[i]=0; if(!su.empty()) val[i]+=a[su.begin()->o].sec; if(!sd.empty()) val[i]+=a[sd.begin()->o].sec; } ans=0; solve(); for(int i=1;i<=2*n;i++) pos[i]=-pos[i]; for(int i=1;i<=n;i++) swap(pos[i],pos[2*n-i+1]),swap(val[i],val[2*n-i]); solve(); printf("%.15Lf\n",ans); } }