ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural SU and Orel STU contest. Petrozavodsk training camp. Summer 2006

About     Problems     Submit solution     Judge status     Standings
Contest is over

F. Farm 2

Time limit: 1.0 second
Memory limit: 64 MB
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 from voting.
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
1 -1
Problem Author: Alexander Ipatov
Problem Source: Ural SU and Orel STU Contest. Petrozavodsk Summer Session, August 2006
To submit the solution for this problem go to the Problem set: 1473. Farm 2