Here is a farm. A farmer breeds camels, sheep, and green cockroaches. When a new
animal is born on the farm, the farmer has to know which kind it is.
He can recognize cockroaches from other animals himself, but to
distinguish a camel from a sheep he needs help in the form of a
commission of experts. The commission measures two parameters of
a new-born animal: the hump's height and the horns' length.
Using this data, the experts determine the kind of the animal
(camel or sheep).
The decision-making process is the following.
The ith expert chooses two integers ai
and bi with absolute values not exceeding 2∙109.
For an animal with parameters (A, B), the expert
calculates the value (aiA + biB).
If this value is positive, then the expert decides that this is a
camel, if the value is negative, then the animal is a sheep, and
if the value is zero, then the expert is at a loss and abstains
The commission makes a decision with respect to each animal by voting.
If strictly more than half of experts think that the animal is a camel,
then the commission reports to the farmer that his new animal is a camel.
A similar rule applies to the case when strictly more than half of experts
believe that the animal is a sheep. And if the commission cannot identify
the animal as a camel or a sheep, then the farmer judges that he has
one more green cockroach.
Once the farmer decided that it is too expensive to pay so many
experts. Indeed, if, for example, the commission consists of four
people, and the first expert fully agrees with the third one, and
the second expert makes the same decisions as the fourth expert,
then there is no sense to keep the third and the fourth experts.
There are N confirmed camels and sheep on the farm
already. The farmer wants to determine the minimal K
such that the commission of K experts can recognize
all the camels as camels, and all the sheep as sheep
(i.e., there exist pairs of numbers ai
and bi such that all the animals on the farm
are recognized by the commission correctly).
The first line contains the total number of camels and sheep
on the farm N (1 ≤ N ≤ 10000).
Each of the next N lines contains three integers, which
describe the jth animal: Aj is the hump's height,
Bj is the horns' length, and
Cj is the kind of the animal (1 denotes a camel and
2 denotes a sheep).
0 ≤ Aj, Bj ≤ 10000.
If there is no commission satisfying the farmer's requirements,
then output the number –1. Otherwise, in the first line output
the minimal number of experts K, and in the next K
lines output the numbers ai and
bi separated by a space.
You may output any coefficients such that an expert
commission using them will make a correct decision with respect
to each of the N animals.
10 0 1
0 10 2
Problem Author: Alexander Ipatov
Problem Source: Ural SU and Orel STU Contest. Petrozavodsk Summer Session, August 2006