#P17915. Regional Champion

Regional Champion

题目描述

在平面上画 nn 个圆、mm 个三角形和 kk 条无限延伸的直线,使这些图形的边界将平面分割成尽可能多的区域。

请输出最多能得到多少个区域,并给出一组达到最大值的图形坐标。圆只绘制圆周,三角形只绘制三条边;它们的内部不是被涂满的区域。

输入格式

第一行是测试组数 TT。随后每组数据占一行,包含三个整数 n,m,kn,m,k。

输出格式

每组数据依次输出:

  1. 一行一个整数,表示最大区域数。
  2. nn 行,每行三个整数 x,y,Rx,y,R,表示圆心和半径。
  3. mm 行,每行六个整数 x1,y1,x2,y2,x3,y3x_1,y_1,x_2,y_2,x_3,y_3,表示一个三角形的三个顶点。
  4. kk 行,每行四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2,表示一条直线经过的两个不同点。

所有坐标都必须在 [−1000,1000][-1000,1000] 内,半径必须在 [1,1000][1,1000] 内。三角形必须由三个不同且不共线的顶点构成。

满足要求的构造不唯一,输出任意一种即可。可以证明,给定整数坐标和半径范围不会妨碍取得最大区域数。

数据范围

1≤T≤50001\le T\le5000,0≤n,m,k≤1000\le n,m,k\le100,n+m+k>0n+m+k>0。

一个输入文件中,所有测试组的 max⁡(n,m,k)3\max(n,m,k)^3 之和不超过 10710^7。

样例

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