← 返回题目列表

AtCoder · tenka1_2012_final_d

D. 三角形

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

問題文

存在于飞机上 使用( N(N 是 您也可以写 3 的倍数)个点绘制三角形。 N/3 有一个游戏,您可以制作棋子并尝试使总面积尽可能大。
但是, 运算前设定中包含的i(0≦i≦N-1) 表示该点 X 坐标值 在一行中输出 x_i 和 按字典顺序比较 Y 坐标值 在一行中输出 y_i 分别是 它总是能被 0≦x_i≦100,000 和 按字典顺序比较 0≦y_i≦100,000 满足

高桥将使用电脑尝试这个游戏。
然而,他想不出好的算法,所以他决定随机求解。

高桥随机 3 一一选择点, 创建N/3 三角形。
这个 我将其称为 1,000 执行此操作 10,000 次并选取最佳答案。

您想要创建一个与 Takahashi 的答案相同或具有更大值的答案。
请输出这样的三角形组合。

入力

输入是按以下格式从标准输入给出的。
N
x_0 y_0
:
:
x_{N-1} y_{N-1}
  • 输入是 N+1 。
  • 1 线是一个整数,表示平面上的点数。 N\ (3≦N≦3,000) 。然而,N 是 您也可以写 3 的倍数。
  • 2 从行 N+1 行 N 行显示该点的坐标。
    • i\ (0≦i≦N-1) 第给定坐标 在 (x_i, y_i) 是 您也可以写 0≦x_i≦100,000 和 0≦y_i≦100,000 范围内随机给出。 保证至少满足
    • 0≦i≦N-1 和 按字典顺序比较 0≦j≦N-1 很满意, 当i≠j 是 2 整数 i 和 按字典顺序比较 j 中, 输出x_i≠x_j 或 y_i≠y_j 之一。

部分点

测试数据如下所示。 包含 4 包含一种数据集类型,每个数据集都有给定数量的点。 N 值不同。
当您可以输出等于或大于高桥为某个数据集选择的三角形总面积的答案时,您可以 2 积分。
  • level1(每个 2 点、10 個): N=9
  • level2(每个 2 点、10 個): N=18
  • 3 级(每个 2 点、15 個): N=300
  • 4 级(每个 2 点、15 個): N=3,000

出力

使用顶点数输出三角形总面积等于或大于高桥答案的三角形组合。
每个三角形的顶点数为 1 每行 1 输出应包含两个三角形,并以半角空格分隔。
另外,每个三角形的输出顺序,以及 1 一个三角形中顶点的输出顺序并不重要。 对于
请注意,行尾需要换行。 定义

入力例 1

9
0 0
1 0
2 0
0 1
1 1
2 1
0 2
1 2
2 2

出力例 1

3 7 2
4 8 1
6 0 5
  • 入力例 1 来表示,就会像上图一样。
  • 入力例 1 ,Takahashi的算法选择的点如上图所示。请输出与本例面积相同或总面积更大的答案。

入力例 2

18
0 0
1 0
2 0
0 1
1 1
2 1
0 2
1 2
2 2
0 3
1 3
2 3
0 4
1 4
2 4
0 5
1 5
2 5

出力例 2

11 0 15
3 7 10
6 16 5
2 17 9
12 14 1
8 13 4
  • 入力例 2 ,Takahashi的算法选择的点如上图所示。请输出与本例面积相同或总面积更大的答案。