#P17993. Three Castles
Three Castles
Three Castles
题目描述
平面上有 个点,编号为 。所有点互不相同,且任意三点不共线。
你需要将这些点划分为三个非空集合,满足:
- 每个点恰好属于一个集合。
- 每个集合中的所有点都是该集合凸包的顶点。只含一个点或两个点的集合也合法。
- 三个集合的闭凸包两两没有公共点,边界接触和内部相交都不允许。
对所有满足 的正整数无序三元组 ,求出哪些三元组能够成为三个集合的大小,并为每个可行三元组输出一种划分。
输入格式
第一行一个整数 。接下来 行,每行两个整数 ,表示第 个点的坐标。
输出格式
第一行输出可行的无序大小三元组数量 。
接下来 行,每行输出 个整数:先输出三个集合的大小 ,随后依次输出第一个集合的 个点编号、第二个集合的 个点编号、第三个集合的 个点编号。
每个可行的无序大小三元组必须恰好输出一次。三个集合之间、各集合内点的顺序以及各行的顺序均可任意。不存在可行划分时输出 0。
数据范围
,。点互不重合,任意三点不共线。
样例输入
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
样例说明
可行的无序大小三元组为 、、; 不可行。样例输出仅为一种合法答案。