我在竞争激烈的编码网站上练习时遇到了这个问题.在经过深思熟虑后,我提到了下面提到的逻辑,但不知何故,我无法通过大多数测试用例.此外,该网站没有透露测试用例,所以我对可能出现的问题一无所知.问题描述如下:
问题陈述
一群大猩猩在马戏团中表演,并且位于多个杆上.两极将其基部浸入水中.您将获得2-D平面中所有极点的x和y坐标.由于大猩猩不会游泳,所以他们从一个极移到另一个极的唯一方法就是跳跃.然而,当一只大猩猩从一个杆跳到另一个杆时,他跳下的杆被深深地淹没了1个单位.请注意,只有被跳下的杆才会被淹没.被跳到的杆不受影响.对于马戏团的高潮,所有大猩猩必须在一个杆上相遇.所有大猩猩的跳跃能力即"J"都给你.跳跃能力只不过是一次跳跃中大猩猩可以覆盖的距离.只有当A和B之间的几何距离小于或等于"J"即跳跃能力时,大猩猩才能从极A跳到B. 每根杆子都有一个高于水面的给定高度,因此固定数量的大猩猩可以从每个杆上跳下,之后它会被淹没.如果极点从0到N-1编号,则需要确定在马戏团高潮期间所有大猩猩可能遇到的极点.假设大猩猩可以在4极中的所有杆上相遇,则打印0 1 2 3.如果它们只能在0和4极上相遇,则打印0 4.如果它们无法在任何杆上相遇,则打印-1.根据上述条件,大猩猩可以进行任意数量的跳跃.
输入
第一行是整数N,表示极数.
第二行是十进制J,表示所有大猩猩的跳跃能力.
连续的N条线包括:
xi =极点的x坐标,yi =极点的y坐标,gi =极点上的大猩猩的初始数量,hi =最初在水面上的极点的高度.
产量
打印大猩猩可能遇到的两极的序列号.如果他们无法在任何地方见面,请打印-1.
约束
1 <= N <= 100
0 <= J <= 100000
-10000 <= xi,yi <= 10000
0 <= gi <= 25
1 <= hi <= 200
样本测试案例
输入
3 30.0
1 10 5 20
5 10 5 20
8 10 5 20
产量
0 1 2
说明
所有杆之间的距离<30.0,因此当距离时,所有大猩猩都可以跳任何杆到任何其他杆.此外,所有杆的高度即20>否.在每个杆上都有大猩猩,所以大猩猩可以通过直接跳跃它们轻松地在0号,1号或2号杆上相遇.
途径
让我们存储2-D整数数组中给出的所有信息.
// 4 columns to store xi, yi, gi and hi for …