logo AlgoBeat OnlineJudge
登录 注册

#101074. [BZOJ 1074] [SCOI2007]折纸origami

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

桌上有一张边界平行于坐标轴的正方形纸片,左下角的坐标为 ,右上角的坐标为 。接下来执行 条折纸命令。每条命令用两个不同点 来表示,执行时把当前的折纸作品沿着 所在直线折叠,并把有向线段 的右边折向左边(左边的部分保持不变)。

折叠结束后,需要在作品上打一个孔,然后用绳子穿起来挂在墙上。孔的位置是相当重要的:若需要穿过太多层的纸,打孔本身比较困难;若穿过的层数太少,悬挂起来以后作品可能会被撕破。为了选择一个比较合适的打孔位置,你需要计算在每个候选位置打孔时穿过的层数。如果恰好穿过某一层的边界(误差 内),则该层不统计在结果中。

本题考虑一个简化的模型:纸的厚度不计,因此折纸操作总能完美执行。

输入格式

输入第一行为一个整数 ,即折纸的次数。以下 行每行四个实数 ,表示每次折纸时对应的有向线段。

下一行包含一个正整数 ,即候选位置的个数,以下每行包含两个实数 ,表示一个候选位置。

输出格式

每个候选位置输出一行,包含一个整数,即该位置打孔时穿过的层数。

样例

样例输入 #1

2
-0.5 -0.5 1 1
1 75 0 75
6
10 60
80 60
30 40
10 10
50 50
20 50

样例输出 #1

4
2
2
0
0
2

数据范围与提示

的数据满足:

的数据满足:

没有写明来源