华师一附中OI组

标题: 2268: 计算几何 [打印本页]

作者: admin 时间: 2021-10-30 07:49
标题: 2268: 计算几何
题目描述
花花对计算几何有着浓厚的兴趣。他经常对着平面直角坐标系发呆，思考一些有趣的问题。今天，他想到了一个十分有意思的题目：首先，花花会在x 轴正半轴和y 轴正半轴分别挑选n 个点。随后，他将x 轴的点与y 轴的点一一连接，形成n 条线段，并保证任意两条线段不相交。花花确定这种连接方式有且仅有一种。最后，花花会给出m 个询问。对于每个询问，将会给定一个点P(xp, yp)，问线段OP（O 为坐标原点）与n 条线段会产生多少个交点？
输入格式
第1 行包含一个正整数n，表示线段的数量；
第2 行包含n 个正整数，表示花花在x 轴选取的点的横坐标；
第3 行包含n 个正整数，表示花花在y 轴选取的点的纵坐标；
第4 行包含一个正整数m，表示询问数量；
随后m 行，每行包含两个正整数xp 和yp，表示询问中给定的点的横、纵坐标。
输出格式
共m 行，每行包含一个非负整数，表示你对这条询问给出的答案。
输入样例复制
3
4 5 3
3 5 4
2
1 1
3 3
输出样例复制
0
3
数据范围与提示
3 条线段分别为：(3, 0) - (0,3)、(4, 0) - (0, 4)、(5, 0) - (0, 5)
(0, 0) - (1,1) 不与他们有交点，答案为0。
(0,0) -(3, 3) 与三条线段均有交点，答案为3。

作者: admin 时间: 2021-10-30 07:50
线段相交是计算几何的基本

欢迎光临华师一附中OI组 (http://hsyit.cn/)