#P17915. Regional Champion
Regional Champion
题目描述
在平面上画 个圆、 个三角形和 条无限延伸的直线,使这些图形的边界将平面分割成尽可能多的区域。
请输出最多能得到多少个区域,并给出一组达到最大值的图形坐标。圆只绘制圆周,三角形只绘制三条边;它们的内部不是被涂满的区域。
输入格式
第一行是测试组数 。随后每组数据占一行,包含三个整数 。
输出格式
每组数据依次输出:
- 一行一个整数,表示最大区域数。
- 行,每行三个整数 ,表示圆心和半径。
- 行,每行六个整数 ,表示一个三角形的三个顶点。
- 行,每行四个整数 ,表示一条直线经过的两个不同点。
所有坐标都必须在 内,半径必须在 内。三角形必须由三个不同且不共线的顶点构成。
满足要求的构造不唯一,输出任意一种即可。可以证明,给定整数坐标和半径范围不会妨碍取得最大区域数。
数据范围
,,。
一个输入文件中,所有测试组的 之和不超过 。
样例
3
1 0 1
0 1 1
1 1 2
4
0 0 1
-2 0 2 0
4
0 0 0 2 2 0
0 1 1 0
18
3 4 2
2 7 2 1 6 4
3 4 6 4
3 3 3 5