#P18162. Touching Grass
Touching Grass
Touching Grass
Adamant 的草坪上长着 株草,编号 。把草坪画在平面上:地面是直线 ,草竖直向上生长。第 株草可以看成从 到 的竖直线段。
Adamant 会移动他的手 次。每次他从 沿直线移动到 。若这条线段与第 株草的线段(包括端点)相交,则称他碰到了第 株草。
对每次移动,判断他是否会碰到草;若会,输出任意一株被碰到的草的编号,否则输出 -1。
输入格式
第一行一个整数 ()。
接下来 行,每行两个整数 (),表示一株草。保证所有草的 互不相同。
下一行一个整数 ()。
接下来 行,每行四个整数 ()。保证 都不等于任何草的 。
输出格式
对每次移动输出一行:被碰到的草的编号(任意一株),若没有则输出 -1。
样例
输入:
3
2 3
6 4
4 5
3
1 4 7 6
7 4 1 2
1 6 1 6
输出:
3
1
-1
(第二行的答案也可以是其它被碰到的草。)