QOJ.ac

QOJ

Time Limit: 1.5 s Memory Limit: 128 MB

# 7464. Self Adjusting Top Tree

Statistics

平面上有 $n$ 条线段。

共 $m$ 次询问,每次询问给出一个边平行于坐标轴的矩形,问 每条与矩形有交的线段与矩形的交的长度之和 与 所有线段的长度之和 的 比值,要求输出与标准答案的相对误差或绝对误差不超过 $10^{-6}$。

线段以 $x_1\;y_1\;x_2\;y_2$ 的形式给出,表示以 $(x_1,y_1),(x_2,y_2)$ 为端点的线段,保证任意两条线段没有交点或重合部分,且 $x_1\ne x_2,y_1\ne y_2$。

矩形以 $x_1\;y_1\;x_2\;y_2$ 的形式给出,表示矩形 $\{(x,y)|x_1\le x\le x_2,y_1\le y\le y_2\}$,保证 $x_1< x_2, y_1< y_2$。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行,每行四个由空格分隔的整数 $x1,y1,x2,y2$,表示线段。

接下来一行一个整数 $m$。

接下来 $m$ 行,每行四个由空格分隔的整数 $x1,y1,x2,y2$,表示询问的矩形。

输出格式

对每个询问,输出一行,一个介于 $0$ 和 $1$ 之间的十进制小数,表示答案

样例数据

样例输入

2
1 1 4 4
2 1 4 3
4
1 1 6 6
1 1 3 3
2 1 3 3
1 2 2 4

样例输出

1
0.6
0.4
0

子任务

Idea:nzhtl1477&ccz181078,Solution:ccz181078,Code:ccz181078,Data:ccz181078

对于 $100\%$ 的数据,$1\le n,m\le 10^5, 1\le x_1,y_1,x_2,y_2\le 10^6$。