Farm 2#4917
There is a farm where a farmer breeds camels, sheep, and green cockroaches. When a new animal is born on the farm, the farmer must determine what kind of animal it is. The farmer can distinguish cockroaches from other animals himself, but to tell a camel apart from a sheep, he needs help from a commission of experts. The commission measures two parameters of the newborn animal: the height of its hump and the length of its horns. Using this data, the experts decide whether the animal is a camel or a sheep.
The procedure is as follows. The -th expert chooses two integers a_i and b_i, each with an absolute value not exceeding 2^{31} - 1. For an animal with parameters (where is the hump height and is the horn length), the expert computes the value a_i A + b_i B. If this value is positive, the expert decides the animal is a camel; if negative, a sheep; and if zero, the expert abstains from voting.
The commission makes its decision by voting. If strictly more than half of the experts consider the animal a camel, then the commission reports to the farmer that a camel has been born. Similarly, if strictly more than half believe it is a sheep, the commission reports a sheep. If the commission cannot identify the animal as either a camel or a sheep, the farmer concludes it was a green cockroach.
At some point, the farmer decides that it is too expensive to pay so many experts. Indeed, if, for example, the commission has four members and the first expert always agrees with the third, while the second always agrees with the fourth, then it makes sense to dismiss the third and fourth experts without losing any decision quality. There are already confirmed camels and sheep on the farm (for each animal, its type is known). The farmer wants to find the minimal such that a commission of experts can always correctly classify all existing camels as camels and all sheep as sheep (that is, there exist pairs of numbers a_i and b_i so that every animal is correctly classified by the commission).
The first line contains the integer (1 \leq N \leq 10000) — the total number of camels and sheep. Each of the following lines contains three integers: A_j (0 \leq A_j \leq 10000), the height of the hump; B_j (0 \leq B_j \leq 10000), the length of the horns; and C_j ( if the animal is a camel, if it is a sheep).
If no such commission exists that satisfies the farmer's requirements, print . Otherwise, print the minimal number , and in the next lines print pairs a_i and b_i, separated by spaces. Any coefficients such that the commission, using them, makes all animal identifications correctly, are acceptable.
Örnek 1