logo AlgoBeat OnlineJudge
登录 注册

#214458. [JOISC 2019] 两个天线 / Two Antennas

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

个天线,沿直线从 编号。每两个相邻天线之间的距离为 1 千米。天线 )的高度为 。天线 可以向距离其 千米至 千米(含端点)范围内的天线发送信息。当且仅当天线 与天线 )能够互相发送信息时,这对天线处于通信状态,其通信成本为

JOI 共和国总理 K 先生已收到市民关于通信不良的 项投诉。一项研究表明,对于第 项投诉(),天线 中的某些天线存在故障。你的任务是判断在天线 中是否存在一对处于通信状态的天线;若存在,还需找出所有此类天线对中的最大通信成本。

编写一个程序,在给定天线信息和投诉信息后,判断在天线 中是否存在一对处于通信状态的天线,并在存在时计算出所有此类天线对中的最大通信成本。

输入格式

从标准输入读取以下数据。输入中的所有数值均为整数。

第一行一个整数

接下来的 行,每行三个整数表示

然后一行一个整数

最后 行每行两个整数表示

输出格式

向标准输出写入 行。第 行()应为 ,若在天线 中不存在任何处于通信状态的天线对;否则,输出所有此类天线对中的最大通信成本。

样例

样例输入 1

5
10 2 4
1 1 1
2 1 3
1 1 1
100 1 1
5
1 2
2 3
1 3
1 4
1 5

样例输出 1

-1
1
8
8
99

数据范围与提示

样例 1 解释

天线 1 与天线 2 之间无法通信,因此第 1 项投诉的答案为

对于第 2、3、4、5 项投诉,通信成本最大的通信天线对分别为

数据范围

  • )。
  • )。
  • )。

子任务

  1. (2 分)
  2. (11 分)
  3. (22 分)
  4. (65 分)无额外约束。

翻译由 Qwen3-235B 完成