P8134 [ICPC 2020 WF] Opportunity Cost

ICPC2020 WF G

正如大多数类型的产品一样，购买新手机可能是困难的。主要的挑战之一是手机有很多不同的方面可能会影响你的选择，比如价格、性能和用户友好性。通常情况下，不会有一款手机在所有这些方面都是最好的：最便宜的手机、最强大的手机和最用户友好的手机可能是不同的手机。 因此，在购买手机时，你必须在你关心的不同方面之间做出一些妥协，选择一款在这些方面达到最佳平衡的手机（当然，“最佳”取决于你的优先级是什么）。衡量这种妥协的一种方法被称为*机会成本*，在这个问题中，我们将其定义如下。 假设你购买了一款价格为 $x$、性能为 $y$、用户友好性为 $z$ 的手机。为了简化问题，我们假设这三个值是在一个可比较的数值尺度上测量的，数值越高越好。如果有 $n$ 款可用的手机，并且 $(x_i, y_i, z_i)$ 表示第 $i$ 款手机的（价格、性能、用户友好性），那么你手机的机会成本定义为 $$\max _{1 \leq i \leq n}\left(\max \left(x_{i}-x, 0\right)+\max \left(y_{i}-y, 0\right)+\max \left(z_{i}-z, 0\right)\right)$$ 编写一个程序，给定可用手机的列表，找到机会成本最小的手机。

输入的第一行包含一个整数 $n$ ($2 \leq n \leq 200,000$)，表示考虑的手机数量。接下来的 $n$ 行中，第 $i$ 行包含三个整数 $x_i$、$y_i$ 和 $z_i$，其中 $x_i$ 是价格，$y_i$ 是性能，$z_i$ 是第 $i$ 款手机的用户友好性（$1 \leq x_i, y_i, z_i \leq 10^9$）。

输出一行，包含两个整数：最小可能的机会成本和一个介于 $1$ 到 $n$ 之间的整数，表示实现该机会成本的手机。如果有多部这样的手机，输出索引最小的那一部。

题面翻译由 ChatGPT-4o 提供。