#P17993. Three Castles

Three Castles

Three Castles

题目描述

平面上有 nn 个点,编号为 1,2,…,n1,2,\ldots,n。所有点互不相同,且任意三点不共线。

你需要将这些点划分为三个非空集合,满足:

  • 每个点恰好属于一个集合。
  • 每个集合中的所有点都是该集合凸包的顶点。只含一个点或两个点的集合也合法。
  • 三个集合的闭凸包两两没有公共点,边界接触和内部相交都不允许。

对所有满足 s1+s2+s3=ns_1+s_2+s_3=n 的正整数无序三元组 {s1,s2,s3}\{s_1,s_2,s_3\},求出哪些三元组能够成为三个集合的大小,并为每个可行三元组输出一种划分。

输入格式

第一行一个整数 nn。接下来 nn 行,每行两个整数 xi,yix_i,y_i,表示第 ii 个点的坐标。

输出格式

第一行输出可行的无序大小三元组数量 kk。

接下来 kk 行,每行输出 n+3n+3 个整数:先输出三个集合的大小 s1,s2,s3s_1,s_2,s_3,随后依次输出第一个集合的 s1s_1 个点编号、第二个集合的 s2s_2 个点编号、第三个集合的 s3s_3 个点编号。

每个可行的无序大小三元组必须恰好输出一次。三个集合之间、各集合内点的顺序以及各行的顺序均可任意。不存在可行划分时输出 0。

数据范围

3≤n≤403\le n\le40,−106≤xi,yi≤106-10^6\le x_i,y_i\le10^6。点互不重合,任意三点不共线。

样例输入

7
4 2
2 1
3 4
1 3
3 3
0 4
2 0

样例输出

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

样例说明

可行的无序大小三元组为 (1,2,4)(1,2,4)、(1,3,3)(1,3,3)、(2,2,3)(2,2,3);(1,1,5)(1,1,5) 不可行。样例输出仅为一种合法答案。