CF733D.Kostya the Sculptor

普及/提高-

通过率:0%

时间限制:3.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Kostya is a genial sculptor, he has an idea: to carve a marble sculpture in the shape of a sphere. Kostya has a friend Zahar who works at a career. Zahar knows about Kostya's idea and wants to present him a rectangular parallelepiped of marble from which he can carve the sphere.

Zahar has n stones which are rectangular parallelepipeds. The edges sizes of the i-th of them are a__i, b__i and c__i. He can take no more than two stones and present them to Kostya.

If Zahar takes two stones, he should glue them together on one of the faces in order to get a new piece of rectangular parallelepiped of marble. Thus, it is possible to glue a pair of stones together if and only if two faces on which they are glued together match as rectangles. In such gluing it is allowed to rotate and flip the stones in any way.

Help Zahar choose such a present so that Kostya can carve a sphere of the maximum possible volume and present it to Zahar.

科斯佳是一位天才雕塑家,他有一个创意:雕刻一座球形的大理石雕塑。科斯佳有一位朋友扎哈尔,他在采石场工作。扎哈尔得知了科斯佳的这个想法,便想送给他一块长方体形状的大理石,以便他从中雕刻出球体。

扎哈尔有 nn 块长方体形状的石料。第 ii 块石料的三条棱长分别为 aia_i、bib_i 和 cic_i。他最多只能挑选其中两块送给科斯佳。

如果扎哈尔选择两块石料,则必须将它们沿某一个面粘合,从而得到一块新的长方体大理石。因此,仅当两块石料用于粘合的两个面(作为矩形)完全相同时,才能将它们粘合在一起。在粘合过程中,允许以任意方式旋转或翻转石料。

请帮助扎哈尔选择一份合适的礼物,使得科斯佳能从中雕刻出体积尽可能大的球体,并将该球体回赠给扎哈尔。

输入格式

The first line contains the integer n (1 ≤ n ≤ 105).

n lines follow, in the i-th of which there are three integers a__i, b__i and c__i (1 ≤ a__i, b__i, c__i ≤ 109) — the lengths of edges of the i-th stone. Note, that two stones may have exactly the same sizes, but they still will be considered two different stones.

第一行包含一个整数 nn(1≤n≤1051 \leq n \leq 10^5)。

接下来有 nn 行,其中第 ii 行包含三个整数 aia_i、bib_i 和 cic_i(1≤ai,bi,ci≤1091 \leq a_i, b_i, c_i \leq 10^9),表示第 ii 块石头的三条边长。注意,两块石头的尺寸可能完全相同,但它们仍被视为两块不同的石头。

输出格式

In the first line print k (1 ≤ k ≤ 2) the number of stones which Zahar has chosen. In the second line print k distinct integers from 1 to n — the numbers of stones which Zahar needs to choose. Consider that stones are numbered from 1 to n in the order as they are given in the input data.

You can print the stones in arbitrary order. If there are several answers print any of them.

第一行输出 k(1 ≤ k ≤ 2),表示扎哈尔所选择的石头数量。
第二行输出 k 个互不相同的整数,取值范围为 1 到 n —— 表示扎哈尔需要选择的石头编号。注意:石头按输入数据中的顺序编号为 1 到 n。

石头的输出顺序可以任意。若存在多个可行答案,输出任意一个即可。

输入输出样例

  • 输入#1

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

    输出#1

    1
    1
  • 输入#2

    7
    10 7 8
    5 10 3
    4 2 6
    5 5 5
    10 2 8
    4 2 1
    7 7 7

    输出#2

    2
    1 5

说明/提示

In the first example we can connect the pairs of stones:

  • 2 and 4, the size of the parallelepiped: 3 × 2 × 5, the radius of the inscribed sphere 1
  • 2 and 5, the size of the parallelepiped: 3 × 2 × 8 or 6 × 2 × 4 or 3 × 4 × 4, the radius of the inscribed sphere 1, or 1, or 1.5 respectively.
  • 2 and 6, the size of the parallelepiped: 3 × 5 × 4, the radius of the inscribed sphere 1.5
  • 4 and 5, the size of the parallelepiped: 3 × 2 × 5, the radius of the inscribed sphere 1
  • 5 and 6, the size of the parallelepiped: 3 × 4 × 5, the radius of the inscribed sphere 1.5

Or take only one stone:

  • 1 the size of the parallelepiped: 5 × 5 × 5, the radius of the inscribed sphere 2.5
  • 2 the size of the parallelepiped: 3 × 2 × 4, the radius of the inscribed sphere 1
  • 3 the size of the parallelepiped: 1 × 4 × 1, the radius of the inscribed sphere 0.5
  • 4 the size of the parallelepiped: 2 × 1 × 3, the radius of the inscribed sphere 0.5
  • 5 the size of the parallelepiped: 3 × 2 × 4, the radius of the inscribed sphere 1
  • 6 the size of the parallelepiped: 3 × 3 × 4, the radius of the inscribed sphere 1.5

It is most profitable to take only the first stone.

在第一个例子中,我们可以连接以下石块对:

  • 2 和 4:长方体尺寸为 3 × 2 × 53 \times 2 \times 5,内切球半径为 11;
  • 2 和 5:长方体尺寸为 3 × 2 × 83 \times 2 \times 8 或 6 × 2 × 46 \times 2 \times 4 或 3 × 4 × 43 \times 4 \times 4,对应内切球半径分别为 11、11、1.51.5;
  • 2 和 6:长方体尺寸为 3 × 5 × 43 \times 5 \times 4,内切球半径为 1.51.5;
  • 4 和 5:长方体尺寸为 3 × 2 × 53 \times 2 \times 5,内切球半径为 11;
  • 5 和 6:长方体尺寸为 3 × 4 × 53 \times 4 \times 5,内切球半径为 1.51.5。

或者仅选取单个石块:

  • 1:长方体尺寸为 5 × 5 × 55 \times 5 \times 5,内切球半径为 2.52.5;
  • 2:长方体尺寸为 3 × 2 × 43 \times 2 \times 4,内切球半径为 11;
  • 3:长方体尺寸为 1 × 4 × 11 \times 4 \times 1,内切球半径为 0.50.5;
  • 4:长方体尺寸为 2 × 1 × 32 \times 1 \times 3,内切球半径为 0.50.5;
  • 5:长方体尺寸为 3 × 2 × 43 \times 2 \times 4,内切球半径为 11;
  • 6:长方体尺寸为 3 × 3 × 43 \times 3 \times 4,内切球半径为 1.51.5。

最有利的选择是仅取第一块石块。

输入解题思路,AI测评打分。不知道怎么写?

首页