#P18000. Triangles
Triangles
Triangles
题目描述
平面上有 个整点, 能被 整除。这些点的横坐标构成 的一个排列,纵坐标也构成 的一个排列。
请将所有点划分成 组,每组三个点作为一个三角形的顶点。每个点必须恰好使用一次。三角形可以退化,可以互相相交。
三角形的大小定义为其轴对齐最小包围矩形的周长,即包含它且四边分别平行于坐标轴的最小矩形的周长。一个划分的得分为所有三角形大小之和。
求最大可能得分,并输出一种达到最大值的划分。
输入格式
第一行一个整数 ,满足 且 。
接下来 行,每行两个整数 ,表示一个点。点按照输入顺序从 到 编号。保证横坐标和纵坐标分别是 到 的排列。
输出格式
第一行输出最大得分。
接下来 行,每行三个点的编号,表示一个三角形。三角形的输出顺序、同一三角形三个点的顺序均任意。
样例 1
输入
6
6 5
3 6
5 3
2 4
1 1
4 2
输出
32
2 3 5
6 1 4