← 返回题目列表

Codeforces · 733/D

D. 雕塑家克斯特亚

中文机器翻译题面 查看原题

Kostya是一位和蔼可亲的雕塑家,他有一个想法:雕刻一个球体形状的大理石雕塑。克斯特亚有一个朋友扎哈尔(Zahar),他正在从事职业工作。扎哈尔了解克斯特亚的想法,并想向他展示一个长方体大理石,他可以用它雕刻出球体。

Zahar 有 n 块长方体石头。其中第 i 个的边尺寸为 ai、bi 和 ci。他最多只能拿两块石头交给克斯特亚。

如果扎哈尔拿了两块石头,他应该将它们粘在其中一个面上,以获得一块新的长方体大理石。因此,当且仅当将一对石头粘合在一起的两个面匹配为矩形时,才可以将一对石头粘合在一起。在这种粘合中,允许以任何方式旋转和翻转石头。

帮助扎哈尔选择这样一个礼物,以便克斯特亚可以雕刻一个尽可能大体积的球体并将其赠送给扎哈尔。

输入

第一行包含整数 n (1 ≤ n ≤ 105)。

接下来有 ​​n 行,其中第 i 行有三个整数 ai、bi 和 ci (1 ≤ ai, bi, ci ≤ 109)——第 i 块石头的边长。请注意,两颗宝石可能具有完全相同的尺寸,但它们仍将被视为两颗不同的宝石。

输出

在第一行中打印 k (1 ≤ k ≤ 2) Zahar 选择的石子数量。在第二行中打印 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

注意

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

- 2和4,平行六面体的尺寸:3 × 2 × 5,内接球体的半径1
- 2和5,平行六面体的尺寸:3 × 2 × 8或6 × 2 × 4或3 × 4 × 4,内切球的半径分别为1或1或1.5。
- 2和6,平行六面体的尺寸:3 × 5 × 4,内切球的半径1.5
- 4和5,平行六面体的尺寸:3 × 2 × 5,内接球体的半径1
- 5和6,平行六面体的尺寸:3 × 4 × 5,内切球的半径1.5

或者只拿一颗石头:

- 1 平行六面体的尺寸:5 × 5 × 5,内切球半径2.5
- 2 平行六面体的尺寸:3 × 2 × 4,内接球体的半径1
- 3 平行六面体的尺寸:1 × 4 × 1,内切球半径0.5
- 4 平行六面体的尺寸:2 × 1 × 3,内切球半径0.5
- 5 平行六面体的大小:3 × 2 × 4,内接球体的半径1
- 6 平行六面体的尺寸:3 × 3 × 4,内切球半径1.5

只拿第一块石头是最有利可图的。