IDE
题库
题目列表
题单列表
题目收藏
记录
比赛
公开的比赛
我参与的比赛
用户
用户排名
奖牌排名
外部排名
近期排名
用户对比
用户组列表
博客
集训队
赛事新闻
赛事列表
获奖情况
视频列表
登录
企鹅——高级
1 Sec
64 MB
|
Markdown
显示标签
困难
(*2400)
计算几何
图论
网络流
最大流
8
58
通过
提交
题目描述
在靠近南极的某处,一些企鹅站在许多漂浮的冰块上。由于企鹅是群居动物,所以它们想要聚集到一起,在同一个冰块上。企鹅们不想把自己的身体弄湿,所以它们在冰块之间跳跃,但是它们的跳跃距离,有一个上限。 随着气温的升高,冰块开始融化,并出现了裂痕。而企鹅跳跃的压力,使得冰块的破裂加速。幸运的是,企鹅对冰块十分有研究,它们能知道每块冰块最多能承受多少次跳跃。对冰块的损害只在跳起的时候产生,而落地时并不对其产生伤害。 现在让你来帮助企鹅选择一个冰面使得它们可以聚集到一起。
输入格式
第一行包含一个整数 $N$ $(1 \le N \le 100)$ 和一个浮点数 $D$ $(0 \le D \le 10^5)$,表示冰块的数目和企鹅的最大跳跃距离。 接下来 $N$ 行,每行包含四个整数 $x_i, y_i, n_i, m_i$ $(-10^4 \le x_i, y_i \le 10^4, 0 \le n_i \le 10, 1 \le m_i \le 200)$,分别表示冰块的 X 和 Y 坐标、该冰块上的企鹅数目以及还能承受起跳的次数。
输出格式
输出所有可能的相聚冰块的编号,以 $0$ 开始。如果不能相遇,输出 `-1`.
样例输入 #1
复制
5 3.5 1 1 1 1 2 3 0 1 3 5 1 1 5 1 1 1 5 4 0 1
样例输出 #1
复制
1 2 4
样例输入 #2
复制
3 1.1 -1 0 5 10 0 0 3 9 2 0 1 1
样例输出 #2
复制
-1
题面
提交
记录
统计
上一题
下一题
上传者
coach
创建时间
2012-10-23 21:49
修改时间
2023-08-06 19:09
Markdown 题面
×
登录
×
账号
密码
记住我