Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Difficulty: [show] Hackable ✓
Statistics

Arona wants to win the regional championship. So Plana generates the following problem for Arona based on the keyword "region".

Given three integers $n$, $m$, and $k$, you need to draw $n$ circles, $m$ triangles, and $k$ lines on a plane to divide it into as many regions as possible.

Of course, Arona's drawing skills and mathematical abilities are very poor. So she comes to you for help.

Input

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 5 \times 10^3$) indicating the number of test cases. For each test case:

The first and only line contains three integers $n$, $m$, and $k$ ($0 \le n, m, k \le 100$, $n + m + k > 0$) indicating the number of circles, triangles, and lines.

It is guaranteed that the sum of $(\max(n, m, k))^3$ of all test cases does not exceed $10^7$.

Output

For each test case:

First, output one line containing one integer, indicating the maximum number of regions that can be divided into.

Then output $n$ lines. Each of these lines contains three integers $x$, $y$, and $R$ ($-10^3 \le x, y \le 10^3$, $1 \le R \le 10^3$) separated by a space, representing the coordinates of the center of the circle, as well as the radius of the circle.

Next, output $m$ lines. Each of these lines contains six integers $x_1$, $y_1$, $x_2$, $y_2$, $x_3$, and $y_3$ ($-10^3 \le x_1, y_1, x_2, y_2, x_3, y_3 \le 10^3$, $(x_1, y_1) \ne (x_2, y_2)$, $(x_1, y_1) \ne (x_3, y_3)$, $(x_2, y_2) \ne (x_3, y_3)$) separated by a space, representing the coordinates of the three vertices in the triangle.

At last, output $k$ lines. Each of these lines contains four integers $x_1$, $y_1$, $x_2$, and $y_2$ ($-10^3 \le x_1, y_1, x_2, y_2 \le 10^3$, $(x_1, y_1) \ne (x_2, y_2)$) separated by a space, representing the coordinates of two points on the line.

It can be proven that, even with the limits specified above, we can always reach the optimal answer.

Examples

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

Note

The third sample test case is shown below.

problem_14812_478e31d2dc02ec2ad85e008d91ad27d7.png
problem_14812_c49174cf27c03ed0f97fb330c3e4891b.png

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.