QOJ.ac

QOJ

Límite de tiempo: 5 s Límite de memoria: 2048 MB Puntuación total: 100

#2365. 航班碰撞

Estadísticas

冰岛包裹流通公司(The Icelandic Corporation for Parcel Circulation)是往返于冰岛与世界其他地区之间运输货物的主要承运商。他们最新的创新成果是一条连接欧洲大陆的无人机航线,有多架无人机沿着单一路线往返飞行。

Drone by Hyeri Kim, Pixabay

这些无人机配备了先进的系统,使它们能够在两架无人机靠近时进行避让机动。不幸的是,软件故障导致该系统瘫痪,现在所有的无人机都沿着航线飞行,且无法避免相互碰撞。

在本题中,无人机被视为沿着无限长直线以恒定速度运动的点。每当两架无人机处于同一位置时,它们就会发生碰撞,导致它们偏离飞行路径并坠入大西洋。题目保证无人机的飞行计划不会在任何时刻出现三架或更多无人机在同一位置碰撞的情况。

已知每架无人机当前的位置及其速度。你的任务是通过找出哪些无人机将无限期地继续飞行而不会坠毁,来评估系统故障造成的损失。

输入格式

输入包含:

  • 一行一个整数 $n$ ($1 \le n \le 10^5$),表示无人机的数量。无人机编号从 $1$ 到 $n$。
  • $n$ 行,第 $i$ 行包含两个整数 $x_i$ 和 $v_i$ ($-10^9 \le x_i, v_i \le 10^9$),表示第 $i$ 架无人机在无限长直线上的当前位置和速度。

无人机按 $x$ 坐标递增的顺序给出,且当前没有两架无人机处于同一位置,即对于每个 $i$,满足 $x_i < x_{i+1}$。你可以假设永远不会发生涉及三架或更多无人机的碰撞。

输出格式

输出永远不会坠毁的无人机数量,随后按编号递增的顺序输出这些无人机的索引。

样例

输入格式 1

3
10 15
30 5
50 -1

输出格式 1

1
3

输入格式 2

6
0 3
2 2
3 1
4 3
5 2
6 3

输出格式 2

2
1 6

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
EditorialOpen Official EditorialQingyu- Download

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.