Subway
本题没有可用的提交语言。
Description
Grammy is planning to build subway in Pigeland. She choosed $n$ stations and decided to connect them with the fewest number of subway lines. Each subway line consists of one or more consecutive segments and passes through one or more stations. A subway line should not pass through a station twice. To make things more interesting, Grammy decided to make exactly $a_i$ subway lines pass through the $i$-th station in the final subway plan.
Formally, each subway line can be described using a series of points $p_1,p_2,\dots,p_L$($L\geq 2$), and the full span of the subway line is the union of segments $[p_1,p_2],[p_2,p_3],\dots,[p_{L-1},p_L]$. Each of the stations located on the subway line should be at point $p_i$ for some $i\in [1,L]$. Note that the points $p_i$ are not necessarily subway stations.
In this picture (illustrating the example test case), there are two subway lines. Line 1 passes through $3$ stations and line 2 passes through $2$ stations. The purple stations with a $2$ on the corner are passed through by $2$ subway lines, and the red station with a $1$ on the corner are passed through by $1$ line.
Due to budget limitations, a subway line should not self-intersect, and two subway lines should not intersect outside the stations.
Please help Grammy to find a subway plan using the minimum possible number of subway lines. If there are multiple solutions, output any.
To avoid precision issues, your subway plan should only contain integral points as the segments' ends.
The first line contains an integer $n$ ($1 \leq n \leq 50$), denoting the number of stations.
Each of the following $n$ line contains $3$ integers $x_i,y_i,a_i$ ($-10^3 \leq x_i,y_i \leq 10^3, 1 \leq a_i \leq 50$), denoting that the $i$-th station is located at position $(x_i,y_i)$, and should be passed through by exactly $a_i$ subway lines.
It is guaranteed that the stations have distinct coordinates.
The first line should contain the minimum possible number of subway lines $k$.
Each of the following $k$ lines contains the description of a subway line in the format below:
The first integer in the line $L$ ($2 \leq L$), denoting the total number of endpoints in this subway line.
Followed by $L$ pairs of integers $x_i,y_i$($-10^9\leq x_i,y_i \leq 10^9$) denoting the endpoints of this subway line.
The sum of $L$ in your output should not exceed $10^4$.
Input
The first line contains an integer $n$ ($1 \leq n \leq 50$), denoting the number of stations.
Each of the following $n$ line contains $3$ integers $x_i,y_i,a_i$ ($-10^3 \leq x_i,y_i \leq 10^3, 1 \leq a_i \leq 50$), denoting that the $i$-th station is located at position $(x_i,y_i)$, and should be passed through by exactly $a_i$ subway lines.
It is guaranteed that the stations have distinct coordinates.
Output
The first line should contain the minimum possible number of subway lines $k$.
Each of the following $k$ lines contains the description of a subway line in the format below:
The first integer in the line $L$ ($2 \leq L$), denoting the total number of endpoints in this subway line.
Followed by $L$ pairs of integers $x_i,y_i$($-10^9\leq x_i,y_i \leq 10^9$) denoting the endpoints of this subway line.
The sum of $L$ in your output should not exceed $10^4$.
3
1 2 1
2 1 2
3 3 2
1
1 1 1
2
3 2 1 1 2 3 3
4 -1 -1 2 1 3 3 4 5
1
5 0 0 1 1 2 2 4 4 8 8