logo AlgoBeat OnlineJudge
登录 注册

#214801. Hit or not?

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

"Jee 这人真有意思,问他空了中了,他说赚了。"


子弹判定是 fps 游戏中老生常谈的问题。

现在我们讨论一个简化版本:

将敌人的身体投影简化为二维平面上的凸多边形,其顶点数为 ,第 个顶点的坐标为 ,顶点以逆时针顺序给出。现在东可站在地图 轴上的点 处,向正前方( 轴正方向)开枪射击,子弹沿射线飞行。由于敌人是凸多边形,子弹只会击中一条边。现在你是游戏设计师,需要找到子弹首先击中的是哪条边。

注意到:由于取样的点越多,凸多边形近似越精确,因此多边形的顶点数可能很大。

输入格式

第一行一个正整数 ,表示凸多边形的顶点数。

接下来 行,每行两个整数 ,以逆时针顺序给出每个顶点坐标。

最后一行一个整数 ,表示点 的横坐标,数据保证点 严格在多边形外部。

保证所有点横坐标两两不同,子弹会射中恰好一条边。

输出格式

输出两个整数 ,表示射线首先碰到的边的两个端点的索引,你可以以任意顺序输出它们。

样例

样例输入 1

3
4 3
13 15
-12 15
2

样例输出 1

3 1