New Online Judge 主页 问题 来源/分类 竞赛&作业 状态 排名 常见问答
登录 注册

2183: 旋转问题

内存限制：512 MB 时间限制：3 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：1 通过：1
提交提交记录统计

题目描述

平面上有 n 个钉子，钉子粗细忽略不计。
给定一根长度为 d 的绳子，一端固定在原点 (0,0)，一端初始位于 (d,0)。
现在绳子逆时针旋转，当碰到钉子后，绳子将绕着钉子继续逆时针旋转。
上述情况将持续发生，由于钉子粗细忽略不计，最终将围绕着某个钉子旋转。

输入格式

第一行为正整数 n 和 d，1≤n≤105,1≤d≤109。
接下来 n 行，每行两个整数 xi,yi，-109≤xi,yi≤109。
所有钉子不在绳子上。

输出格式

输出一个整数 i，表示最终围绕的钉子在输入中的顺序，从 1 开始。
如果不围绕任何钉子旋转，输出 -1。
测试数据保证 d 变化±10-6，不会改变最终结果。

输入样例 复制 

5 200
4 4
4 -4
3 1
-4 4
-4 -4

输出样例 复制 

1

数据范围与提示

来源：2023 NCPC