403787: GYM101300 D Rancho

Breeding of unusual kind of cattle has recently become a very lucrative undertaking. Megacows are an endemic species. Due to the biological factors, their occurrence and breeding possibilities are limited to only one, quite remote part of the Universum.

However, the work in this discipline is not easy at all. Megacows are extremely strong, thus a typical classic fence is not able to restrict them. Fortunately, the plots are equipped with numerous Force Points marked as (FP). These points connected with each other create an energy barrier – efficient fence for this new cattle species.

Prior to the commencement of typical activities at the rancho, every new farmer in this region must face other noxious limitation – the local law. It prohibits any private ownership of the land. The only way of conducting legal breeding is the lease of a plot of land and payment of high taxes to the benefit of the Beetlejumper Land Council. The amount of the tax due depends on the actual area of the territory limited by the energy barrier.

Help the farmers specify the minimum (to reduce the taxes) and the maximum (to specify the potential of the rancho to enlarge the herd) area which may be circled by the energy barrier on a given plot of land.

The task should be accomplished by indicating a proper order of joining the Force Points. Each point may be connected with only two other FPs and the lines connecting these points cannot cross. Additionally in order to make the energy barrier stable enough, you must choose at least (N–K) points from among N points available on a plot of land for the connection.

The first line of a test set includes one natural number T – the number of plots of land, the values of which the farmers would like to know. The subsequent lines include T descriptions of  the plots of land.

The first line of the description of a plot of land consists of two integer numbers separated by a whitespace: N, indicating the number of Force Points available on a plot of land and K – the number of points which may be skipped in order to make the barrier stable enough. Each i-th from among the subsequent N lines includes three integer numbers: c_i, x_i, y_i. The values x_i and y_i are the unique (within the area of a plot of land) coordinates of a given FP, whereas c_i is an identifier (also unique within the area of a plot of land) (see Output).

1 ≤ T ≤ 5

3 ≤ N ≤ 1000

0 ≤ K ≤ 100

1 ≤ c_i ≤ N

0 ≤ x_i, y_i ≤ 10⁴

The output data should include characteristics and definitions indicated for particular plots of land in the order in which these plots appeared in the input file. Each separate description is composed of three lines discussed below.

The first line should consist of a definition of the possible biggest area limited by an energy barrier. This line should start with a natural number L which indicates the number of the used Force Points. Then, after a whitespace, you should place L numbers separated by a single whitespace, which constitute a sequence of c_i identifiers – their connection in a given sequence should create a closed polygonal chain which defines a subjective area. Each identifier may appear only once (the last element is automatically connected with the first one).

The second line is a definition of the possible smallest area limited by the energy barrier. The elements of this definition are analogous to these from the first line.

The third line of a description should consist of the number S which is a product (rounded to the closest integer number) of the number 10 and a difference of the areas listed in the first and second line of a given description. This means: S =  round(10·(a_max - a_min)), where a_max is the area from the first line of the description of the solution for a given plot of land, and a_min is the area from the second line of this description.

If the following conditions are satisfied:

• output data are in the correct format,
• at least (N–K) points (vertices) are used in a definition of each area,
• in a definition of each area every vertex is given at most once,
• in a definition of none area two line segments connecting its subsequent vertices cross each other,
• for each plot of land the surface of the biggest area is not smaller than the surface of the smallest area,
• S value is correctly calculated for each plot of land,

then the score for a given set equals , where S_s is the sum of the S values for all plots of land in a given test set and S_tly is the sum of maximum S_s values achieved by last year's contestants for all test sets. Otherwise the score is 0.

For the input data (this example is not from the official testset, it is just example):

3
8 0
1 2 2
2 2 3
3 1 3
4 1 1
7 1 4
6 3 1
8 1 2
5 3 4
8 2
6 3 3
1 2 1
2 2 2
3 2 3
4 4 1
8 2 4
7 3 2
5 4 4
4 0
2 4 3
1 2 2
3 2 3
4 4 2

A possible correct answer is:

8 7 5 6 4 8 1 2 3
8 7 5 2 1 6 4 8 3
10
6 1 2 3 8 5 4
6 1 2 3 6 7 4
35
4 3 2 4 1
4 3 2 4 1
0

Explanation:

• For the first plot of land, the biggest area a_max is 5, and of the smallest area a_min is 4. The S value is equal to: 10·(5 - 4) = 10.
• For the second plot of land: a_max = 6, a_min = 2.5. Thus S = 10·(6 - 2.5) = 35.
• For the third plot of land: a_max = 2, a_min = 2. Thus S = 10·(2 - 2) = 0.
• Score for all plots of land from this test set: S_s = 10 + 35 + 0 = 45.