13958번 - Bribing Eve 다국어

Eve works at a magazine that does product reviews and publishes recommeendations to consumers. They are working on a new mobile phones review and have decided on two reproducible tests that score each device's battery lifetime and performance using an integer between 1 and 1000.

These two scores, x₁ and x₂, are then combined with a weights vector w=[w₁,w₂] to produce an overall score:

s = w₁x₁ + w₂x₂.

The final review ranking is then obtained by sorting the products by decreasing order of s. Additionally, when multiple products get exactly the same score, Eve decides how to order them. 

Maria (a fake name to mask her identity) tried to bribe Eve to tweak the result to get her product higher on the list. Eve argued that she was not able to tamper the evaluation of each test, but Maria suggested to tweak the weights w used when computing the overall score. The weights w must be non-negative and at least one of them must be positive, but the values are decided by Eve. 

Eve is thinking whether to modify the weights in Maria's benefit or not, and asked you to determine what are the best and worst possible ranking positions for Maria's product.

Given a list of all products scores in battery and performance [x₁,x₂] tests, find out what are the best and worst positions in the ranking that can be given to Maria's product when the weights [w₁,w₂] and the order for tied products are left for Eve to decide. 

The first line has the number N of products being compared. N lines follow, each containing two integers x₁ and x₂ indicating a product's score in the battery and performance tests. Maria's product is the first on the list. 

The output consists of two numbers A and B, indicating the best and worst possible positions that Maria's product can get on the ranking given Eve's ability to modify the weights and ordering in case of a tie. 

• 1 ≤ N ≤ 100000 Number of products
• 1 ≤ x₁,x₂ ≤ 1000 Performance of a product in the tests