F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 1074. -- [SCOI2007]折纸origami

1074: [SCOI2007]折纸origami

Time Limit: 20 Sec  Memory Limit: 162 MB
Submit: 379  Solved: 233
[Submit][Status][Discuss]

Description

  桌上有一张边界平行于坐标轴的正方形纸片,左下角的坐标为(0,0),右上角的坐标为(100,100)。接下来执行
n条折纸命令。每条命令用两个不同点P1(x1,y1)和P2(x2,y2)来表示,执行时把当前的折纸作品沿着P1P2所在直线
折叠,并把有向线段P1P2的右边折向左边(左边的部分保持不变)。折叠结束后,需要在作品上打一个孔,然后用
绳子穿起来挂在墙上。孔的位置是相当重要的:若需要穿过太多层的纸,打孔本身比较困难;若穿过的层数太少,
悬挂起来以后作品可能会被撕破。为了选择一个比较合适的打孔位置,你需要计算在每个候选位置打孔时穿过的层
数。如果恰好穿过某一层的边界(误差0.000001内),则该层不统计在结果中。本题考虑一个简化的模型:纸的厚
度不计,因此折纸操作总能完美执行。

Input

  输入第一行为一个整数n,即折纸的次数。以下n行每行四个实数x1,y1,x2,y2,表示每次折纸时对应的有向线
段。下一行包含一个正整数m,即候选位置的个数,以下每行包含两个实数x,y,表示一个候选位置。0<=n<=8, 1<=
m<=50

Output

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

Sample Input

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

Sample Output

4
2
2
0
0
2

HINT



Source

[Submit][Status][Discuss]

HOME Back