自动搬运

查看原文

来自洛谷，原作者为

	QwQcOrZ AFOed | 印刷成文不能代表它们就是真理 | 极东魔术昼寝结社之夏 | The Great Gig In The Sky

搬运于2025-08-24 22:17:28，当前版本为作者最后更新于2023-03-19 12:52:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一个不需要平衡树的做法。

先将线段分为两类：$x_1<x_2,y_1<y_2$ 和 $x_1<x_2,y_1>y_2$。

只考虑第一种情况，第二种情况翻转坐标系后再做一遍即可。

将询问差分成四个右上角为 $(x,y)$，左下角为 $(-\infty,-\infty)$ 的矩形，那么一个矩形的答案有以下三部分组成：

1. 整个线段都在矩形内，即 $x_2\leq x,y_2\leq y$。
2. 与矩形上边界相交。
3. 与矩形右边界相交。

第一部分是一个二维偏序，扫描线 $+$ 树状数组即可。

第二三部分是同理的，我们只考虑第二部分。

按 $y$ 从低到高扫描线，用 set 维护所有 $y_1\leq y<y_2$ 的线段，顺序是在 $y$ 这个高度的横坐标从左到右。由于线段不会相交，它们的相对位置不会改变，因此可以用 set 直接维护。

考虑如何处理一个询问，在 set 中二分出它所对应的前缀，这个前缀的线段上边界相交。

贡献的处理是简单的，化一下式子可以知道是两个求和的形式。问题在于如何定位出这些线段。

由于线段不相交，那么一定存在一个排列线段的顺序，使得对于每个时刻 set 中的元素在这个排列中的位置都是递增的。

不妨先做一遍扫描线，在插入、删除线段时都让相邻线段之间从左至右连一条有向边，这样可以建立出一张 DAG，这个 DAG 的拓扑序即为一个满足条件的排列。

接下来就好办了，找到前缀所对应的拓扑序最大的线段（也就是 set 中的最后一个与上边界相交的），直接查询一个拓扑序上的前缀和即可。

时间复杂度 $\mathcal O((n+Q)\log n)$。

实际上实现的时候只有第一遍扫描线需要 set，第二遍所需的所有信息都可以在第一遍就处理出来。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
const int M=1e6+5;
const double eps=1e-8;

double dis(double x,double y) {
	return sqrt(x*x+y*y);
}
double cross(double x1,double y1,double x2,double y2) {
	return x1*y2-x2*y1;
}
struct segment {
	int x1,y1,x2,y2;
	double len() {
		return dis(x2-x1,y2-y1);
	}
}a[2][N],b[N];
double get(segment a,double y) {
	if (a.y1==a.y2) {
		return a.x1;
	}
	return (y-a.y1)/(a.y2-a.y1)*(a.x2-a.x1)+a.x1;
}
bool check(segment a,segment b) {
	if (a.x1==a.x2&&a.y1==a.y2&&b.x1<=a.x1&&a.x2<=b.x2&&b.y1<=a.y1&&a.y2<=b.y2&&abs(cross(a.x1-b.x1,a.y1-b.y1,a.x1-b.x2,a.y1-b.y2))<eps) {
		return 0;
	}
	if (b.x1==b.x2&&b.y1==b.y2&&a.x1<=b.x1&&b.x2<=a.x2&&a.y1<=b.y1&&b.y2<=a.y2&&abs(cross(b.x1-a.x1,b.y1-a.y1,b.x1-a.x2,b.y1-a.y2))<eps) {
		return 0;
	}
	double y=max(a.y1,b.y1);
	return get(a,y)<get(b,y);
}
struct bit {
	int n;
	double t[M];
	void send(int _n) {
		n=_n;
		for (int i=1;i<=n;i++) {
			t[i]=0;
		}
	}
	void add(int x,double y) {
		for (;x<=n;x+=x&-x) {
			t[x]+=y;
		}
	}
	double query(int x) {
		double res=0;
		for (;x;x&=x-1) {
			res+=t[x];
		}
		return res;
	}
}t0,t1,tt;
int n,m,p[N],que[N],tmp;
struct cmp {
	bool operator ()(const int &u,const int &v) const {
		return check(a[tmp][u],a[tmp][v]);
	}
};
vector<int>ins[M];
struct Query {
	int x,f,id,pos;
};
vector<Query>q[M];
double ans[N];
vector<int>e[N];
int deg[N],pos[N];
void add_edge(int u,int v) {
	e[u].emplace_back(v);
	deg[v]++;
}
void solve(int n,segment *a,bool flag) {
	for (int i=1;i<=n;i++) {
		e[i].clear();
		deg[i]=0;
	}
	for (int i=1;i<=1e6;i++) {
		ins[i].clear();
		q[i].clear();
	}
	for (int i=1;i<=n;i++) {
		ins[a[i].y1].emplace_back(i);
		ins[a[i].y2].emplace_back(-i);
	}
	for (int i=1;i<=m;i++) {
		q[b[i].y2].emplace_back((Query){b[i].x2,1,i,0});
		q[b[i].y2].emplace_back((Query){b[i].x1,-1,i,0});
		q[b[i].y1].emplace_back((Query){b[i].x2,-1,i,0});
		q[b[i].y1].emplace_back((Query){b[i].x1,1,i,0});
	}
	set<int,cmp>S;
	for (int i=1;i<=1e6;i++) {
		for (int j:ins[i]) {
			if (j>0) {
				auto now=S.insert(j).first;
				if (now!=S.begin()) {
					add_edge(*prev(now),j);
				}
				if (++now!=S.end()) {
					add_edge(j,*now);
				}
			} else {
				j=-j;
				auto now=S.find(j);
				if (now!=S.begin()&&next(now)!=S.end()) {
					add_edge(*prev(now),*next(now));
				}
				S.erase(now);
			}
		}
		for (auto &[x,f,id,pos]:q[i]) {
			a[0]=(segment){x,i,x,i};
			set<int,cmp>::iterator now;
			if (flag) {
				now=S.upper_bound(0);
			} else {
				now=S.lower_bound(0);
			}
			if (now!=S.begin()) {
				pos=*--now;
			}
		}
	}
	int h=1,t=0;
	for (int i=1;i<=n;i++) {
		if (!deg[i]) {
			que[++t]=i;
		}
	}
	while (h<=t) {
		int now=que[h];
		p[now]=h++;
		for (int to:e[now]) {
			if (!--deg[to]) {
				que[++t]=to;
			}
		}
	}
	tt.send(1e6);
	t0.send(1e6);
	t1.send(1e6);
	for (int i=1;i<=1e6;i++) {
		for (int j:ins[i]) {
			if (j>0) {
				t0.add(p[j],a[j].y1*(a[j].len()/(a[j].y2-a[j].y1)));
				t1.add(p[j],a[j].len()/(a[j].y2-a[j].y1));
			} else {
				j=-j;
				t0.add(p[j],-a[j].y1*(a[j].len()/(a[j].y2-a[j].y1)));
				t1.add(p[j],-a[j].len()/(a[j].y2-a[j].y1));
				if (flag) {
					tt.add(a[j].x2,a[j].len());
				}
			}
		}
		for (auto [x,f,id,pos]:q[i]) {
			if (flag) {
				ans[id]+=f*tt.query(x);
			}
			if (pos) {
				ans[id]+=f*(i*t1.query(p[pos])-t0.query(p[pos]));
			}
		}
	}
}

signed main() {
	ios::sync_with_stdio(false),cin.tie(0);
	cout.precision(10),cout.setf(ios::fixed);
	
	cin>>n;
	double sum=0;
	int n1=0,n2=0;
	for (int i=1;i<=n;i++) {
		segment p;
		cin>>p.x1>>p.y1>>p.x2>>p.y2;
		sum+=p.len();
		if (p.x1>p.x2) {
			swap(p.x1,p.x2);
			swap(p.y1,p.y2);
		}
		if (p.y1<p.y2) {
			a[0][++n1]=p;
		} else {
			a[1][++n2]=p;
		}
	}
	cin>>m;
	for (int i=1;i<=m;i++) {
		cin>>b[i].x1>>b[i].y1>>b[i].x2>>b[i].y2;
	}
	
	tmp=0;
	solve(n1,a[0],1);
	for (int i=1;i<=n;i++) {
		swap(a[0][i].x1,a[0][i].y1);
		swap(a[0][i].x2,a[0][i].y2);
	}
	for (int i=1;i<=m;i++) {
		swap(b[i].x1,b[i].y1);
		swap(b[i].x2,b[i].y2);
	}
	solve(n1,a[0],0);
	for (int i=1;i<=n;i++) {
		swap(a[0][i].x1,a[0][i].y1);
		swap(a[0][i].x2,a[0][i].y2);
	}
	for (int i=1;i<=m;i++) {
		swap(b[i].x1,b[i].y1);
		swap(b[i].x2,b[i].y2);
	}
	
	tmp=1;
	for (int i=1;i<=n;i++) {
		a[1][i].y1=1e6+1-a[1][i].y1;
		a[1][i].y2=1e6+1-a[1][i].y2;
	}
	for (int i=1;i<=m;i++) {
		b[i].y1=1e6+1-b[i].y1;
		b[i].y2=1e6+1-b[i].y2;
		swap(b[i].y1,b[i].y2);
	}
	solve(n2,a[1],1);
	for (int i=1;i<=n;i++) {
		swap(a[1][i].x1,a[1][i].y1);
		swap(a[1][i].x2,a[1][i].y2);
	}
	for (int i=1;i<=m;i++) {
		swap(b[i].x1,b[i].y1);
		swap(b[i].x2,b[i].y2);
	}
	solve(n2,a[1],0);
	for (int i=1;i<=n;i++) {
		swap(a[1][i].x1,a[1][i].y1);
		swap(a[1][i].x2,a[1][i].y2);
	}
	for (int i=1;i<=m;i++) {
		swap(b[i].x1,b[i].y1);
		swap(b[i].x2,b[i].y2);
	}
	for (int i=1;i<=m;i++) {
		cout<<ans[i]/sum<<"\n";
	}
	
	return 0;
}