2439 - 奶牛的游戏

题目描述

农民 John的 N (1 \le N \le 1000) 头奶牛 (从 1N 依次编号 )打算玩游戏 Serious Cow Tag。在 Serious Cow Tag这个游戏里,每头牛在牧场网格中取 一个点 (-7500 \le X \le 7500,-7500 \le Y \le 7500) 使得每一对牛的距离都是与众不同的。

奶牛们轮流玩这个游戏,从 #1 号牛开始,然后是 #2, #3, 等等 (只要这头牛仍然参与这个游戏)。每次轮到的玩的牛,会选择一个目前离它最近的牛,走过去拍它一下,然后回到原来的位置,这样那头被拍的牛就被游戏排除在外了。

当只有一头牛留下来了以后,游戏即告结束,那头牛就是赢家。

农民 John 正和邻居们打赌那头牛会赢,所以他想事先知道谁是赢家。写一个 程序,读入每头牛的位置,求那头牛获胜。

输入

Line 1: 一个整数 N , 奶牛的数量。

Lines 2 \dots N+1: 第 i+1 有两个用空格分开的整数,描述第 i 头牛的坐标位置。

输出

Line 1: 获胜的牛的编号。

样例

输入

3
0 0
0 3
4 3

输出

3
说明

1 先走,去拍了离它最近的牛 22 号牛就被删除了,接下去就直接轮到 Cow 3 走。她去拍了 1 号, 1 号被排除,最终 3 号获胜。

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 2 枚
难度 基础


上一题 下一题