如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY-NC-SA 4.0 （除特别声明或转载文章外）
首先，我们只考虑斜率为正的线段，对于斜率为负的，我们把平面倒过来再做一次就行了。
我们发现这题的贡献可减，所以考虑将一个询问拆成四个前缀矩形的询问。
对答案有贡献的线段分为两种，与矩形边界无交和有交的。
无交的线段的右上角一定被包含了，把贡献放在右上角的点上，做一个二维偏序就可以解决；
有交的线段一定只和上边界和右边界之一有交（交在顶点上的扰动一下就变成交在边上了），我们分两遍处理，只考虑与右边界相交的线段。考虑扫描线（一条竖线），维护所有线段与扫描线的交点，由于线段两两不交，交点顺序不会改变，所以考虑用平衡树维护线段到当前扫描线的长度和。查询的时候就是查一个前缀的长度和。
#include<cstdio>
#include<chrono>
#include<random>
#include<cstdlib>
#include<algorithm>
#define BUFSIZE 10000000
struct read{
char buf[BUFSIZE],*p1,*p2,c,f;
read():p1(buf),p2(buf){}
char gc(void){
return p1==p2&&(p2=buf+fread(p1=buf,1,BUFSIZE,stdin),p1==p2)?EOF:*p1++;
}
read& operator >>(int& x){
for(c=gc(),f=0,x=0;c!=EOF&&(c<'0'||c>'9');c=gc())if(c=='-')f=1;
if(f)for(;c>='0'&&c<='9';c=gc())x=x*10-(c-'0');
else for(;c>='0'&&c<='9';c=gc())x=x*10+(c-'0');
return *this;
}
}in;
inline int rand(int l,int r){
return rand()%(r-l+1)+l;
}
int n,m;
struct node{
int x1,x2,y1,y2;
double k,len;
}a[100010];
struct rect{
int x1,x2,y1,y2;
}q[100010];
double S;
double ans[100010];
namespace sub1{
struct node{
double v;
int op,x,y;
node(int o,int a,int b,double val):v(val),op(o),x(a),y(b){}
node():v(),op(),x(),y(){}
}a[500010];
int cnt;
double c[1000010];
void update(int i,double v){
for(;i<=1000000;i+=i&-i) c[i]+=v;
}
double query(int i){
double ans=0;
for(;i;i&=i-1) ans+=c[i];
return ans;
}
void clear(){
cnt=0;
for(int i=1;i<=1000000;i++) c[i]=0;
}
void work(){
std::sort(a+1,a+cnt+1,[](node const &x,node const &y){return x.x==y.x?x.op<y.op:x.x<y.x;});
for(int i=1;i<=cnt;i++)
if(a[i].op==0) update(a[i].y,a[i].v);
else ans[a[i].op]+=a[i].v*query(a[i].y);
}
}
namespace sub2{
double const eps=5e-7;
int cnt,ct,rt;
struct node{
double v1,v2,y;
int op,x;
node(int o,int a,double b,double w1=0,double w2=0):v1(w1),v2(w2),y(b),op(o),x(a){}
node():v1(),v2(),y(),op(),x(){}
}a[600010];
struct nd{
double v1,v2,v3,v4,sum,s;
int ls,rs,tag,sz;
}tr[100010];
void addtag(int x,int v){
if(x){
tr[x].tag+=v;
tr[x].v1+=tr[x].v2*v;
tr[x].v3+=tr[x].v4*v;
tr[x].sum+=tr[x].s*v;
}
}
void pushdown(int x){
if(tr[x].tag){
addtag(tr[x].ls,tr[x].tag);
addtag(tr[x].rs,tr[x].tag);
tr[x].tag=0;
}
}
void pushup(int x){
tr[x].sum=tr[x].v3+tr[tr[x].ls].sum+tr[tr[x].rs].sum;
tr[x].s=tr[x].v4+tr[tr[x].ls].s+tr[tr[x].rs].s;
tr[x].sz=1+tr[tr[x].ls].sz+tr[tr[x].rs].sz;
}
int merge(int x,int y){
if(!x||!y) return x|y;
if(rand(1,tr[x].sz+tr[y].sz)<=tr[x].sz){
pushdown(x);
tr[x].rs=merge(tr[x].rs,y);
pushup(x);
return x;
}else{
pushdown(y);
tr[y].ls=merge(x,tr[y].ls);
pushup(y);
return y;
}
}
void split(int p,double v,int &x,int &y){
if(!p) return x=y=0,void();
pushdown(p);
if(tr[p].v1<=v+eps) x=p,split(tr[x].rs,v,tr[x].rs,y);
else y=p,split(tr[y].ls,v,x,tr[y].ls);
pushup(p);
}
void splitsz(int p,int v,int &x,int &y){
if(!p) return x=y=0,void();
pushdown(p);
if(tr[tr[p].ls].sz<v) x=p,splitsz(tr[x].rs,v-tr[tr[p].ls].sz-1,tr[x].rs,y);
else y=p,splitsz(tr[y].ls,v,x,tr[y].ls);
pushup(p);
}
void del(double x){
int a,b,c;
split(rt,x,a,b);
splitsz(a,tr[a].sz-1,a,c);
rt=merge(a,b);
}
void ins(double x,double a,double b){
++ct;
tr[ct].v1=x,tr[ct].v2=b,tr[ct].v3=0,tr[ct].v4=a;
tr[ct].sum=0,tr[ct].s=tr[ct].v4;
tr[ct].ls=tr[ct].rs=tr[ct].tag=0,tr[ct].sz=1;
int p,d;
split(rt,x,p,d);
rt=merge(p,merge(ct,d));
}
double query(double x){
int a,b;
split(rt,x,a,b);
double ans=tr[a].sum;
rt=merge(a,b);
return ans;
}
void clear(){
cnt=ct=0;
}
int p;
void work(){
p=rt=0;
std::sort(a+1,a+cnt+1,[](node const &x,node const &y){return x.x==y.x?x.op<y.op:x.x<y.x;});
for(int i=1;i<=cnt;i++){
if(p!=a[i].x) addtag(rt,a[i].x-p),p=a[i].x;
if(a[i].op==-1) del(a[i].y);
else if(a[i].op==0) ins(a[i].y,a[i].v1,a[i].v2);
else ans[a[i].op]+=a[i].v1*query(a[i].y);
}
}
}
int main(){
in>>n;
for(int i=1;i<=n;i++){
in>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2;
if(a[i].x2<a[i].x1) std::swap(a[i].x1,a[i].x2),std::swap(a[i].y1,a[i].y2);
a[i].k=1.0*(a[i].y2-a[i].y1)/(a[i].x2-a[i].x1);
S+=(a[i].len=sqrt(1.0*(a[i].x2-a[i].x1)*(a[i].x2-a[i].x1)+1.0*(a[i].y2-a[i].y1)*(a[i].y2-a[i].y1)));
}
in>>m;
for(int i=1;i<=m;i++) in>>q[i].x1>>q[i].y1>>q[i].x2>>q[i].y2;
for(int i=1;i<=n;i++) if(a[i].k>0) sub1::a[++sub1::cnt]=sub1::node(0,a[i].x2,a[i].y2,a[i].len);
for(int i=1;i<=m;i++) sub1::a[++sub1::cnt]=sub1::node(i,q[i].x2,q[i].y2,1),sub1::a[++sub1::cnt]=sub1::node(i,q[i].x1,q[i].y2,-1),sub1::a[++sub1::cnt]=sub1::node(i,q[i].x2,q[i].y1,-1),sub1::a[++sub1::cnt]=sub1::node(i,q[i].x1,q[i].y1,1);
sub1::work();
for(int i=1;i<=n;i++) if(a[i].k>0) sub2::a[++sub2::cnt]=sub2::node(-1,a[i].x2,a[i].y2),sub2::a[++sub2::cnt]=sub2::node(0,a[i].x1,a[i].y1,a[i].len/(a[i].x2-a[i].x1),a[i].k);
for(int i=1;i<=m;i++) sub2::a[++sub2::cnt]=sub2::node(i,q[i].x2,q[i].y2-1e-6,1),sub2::a[++sub2::cnt]=sub2::node(i,q[i].x2,q[i].y1-1e-6,-1),sub2::a[++sub2::cnt]=sub2::node(i,q[i].x1,q[i].y2-1e-6,-1),sub2::a[++sub2::cnt]=sub2::node(i,q[i].x1,q[i].y1-1e-6,1);
sub2::work();
sub2::clear();
for(int i=1;i<=n;i++) if(a[i].k>0) sub2::a[++sub2::cnt]=sub2::node(-1,a[i].y2,a[i].x2),sub2::a[++sub2::cnt]=sub2::node(0,a[i].y1,a[i].x1,a[i].len/(a[i].y2-a[i].y1),1/a[i].k);
for(int i=1;i<=m;i++) sub2::a[++sub2::cnt]=sub2::node(i,q[i].y2,q[i].x2,1),sub2::a[++sub2::cnt]=sub2::node(i,q[i].y2,q[i].x1,-1),sub2::a[++sub2::cnt]=sub2::node(i,q[i].y1,q[i].x2,-1),sub2::a[++sub2::cnt]=sub2::node(i,q[i].y1,q[i].x1,1);
sub2::work();
for(int i=1;i<=m;i++){
q[i].y1=1000001-q[i].y1;
q[i].y2=1000001-q[i].y2;
std::swap(q[i].y1,q[i].y2);
}
for(int i=1;i<=n;i++) a[i].y1=1000001-a[i].y1,a[i].y2=1000001-a[i].y2;
sub1::clear();
for(int i=1;i<=n;i++) if(a[i].k<0) sub1::a[++sub1::cnt]=sub1::node(0,a[i].x2,a[i].y2,a[i].len);
for(int i=1;i<=m;i++) sub1::a[++sub1::cnt]=sub1::node(i,q[i].x2,q[i].y2,1),sub1::a[++sub1::cnt]=sub1::node(i,q[i].x1,q[i].y2,-1),sub1::a[++sub1::cnt]=sub1::node(i,q[i].x2,q[i].y1,-1),sub1::a[++sub1::cnt]=sub1::node(i,q[i].x1,q[i].y1,1);
sub1::work();
sub2::clear();
for(int i=1;i<=n;i++) if(a[i].k<0) sub2::a[++sub2::cnt]=sub2::node(-1,a[i].x2,a[i].y2),sub2::a[++sub2::cnt]=sub2::node(0,a[i].x1,a[i].y1,a[i].len/(a[i].x2-a[i].x1),-a[i].k);
for(int i=1;i<=m;i++) sub2::a[++sub2::cnt]=sub2::node(i,q[i].x2,q[i].y2-1e-6,1),sub2::a[++sub2::cnt]=sub2::node(i,q[i].x2,q[i].y1-1e-6,-1),sub2::a[++sub2::cnt]=sub2::node(i,q[i].x1,q[i].y2-1e-6,-1),sub2::a[++sub2::cnt]=sub2::node(i,q[i].x1,q[i].y1-1e-6,1);
sub2::work();
sub2::clear();
for(int i=1;i<=n;i++) if(a[i].k<0) sub2::a[++sub2::cnt]=sub2::node(-1,a[i].y2,a[i].x2),sub2::a[++sub2::cnt]=sub2::node(0,a[i].y1,a[i].x1,a[i].len/(a[i].y2-a[i].y1),-1/a[i].k);
for(int i=1;i<=m;i++) sub2::a[++sub2::cnt]=sub2::node(i,q[i].y2,q[i].x2,1),sub2::a[++sub2::cnt]=sub2::node(i,q[i].y2,q[i].x1,-1),sub2::a[++sub2::cnt]=sub2::node(i,q[i].y1,q[i].x2,-1),sub2::a[++sub2::cnt]=sub2::node(i,q[i].y1,q[i].x1,1);
sub2::work();
for(int i=1;i<=m;i++) printf("%.6f\n",ans[i]/S+1e-12);
return 0;
}