Hide

Problem B
Bribing Eve

/problems/bribingeve/file/statement/en/img-0001.png

Eve works at a magazine that does product reviews and publishes recommendations 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_1$ and $x_2$, are then combined with a weights vector $w = [w_1, w_2]$ to produce an overall score:

\[ s = w_1 x_1 + w_2 x_2 \, . \]

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 results 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.

Task

Given a list of all products scores in battery and performance $[x_1, x_2]$ 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_1, w_2]$ and the order for tied products are left for Eve to decide.

Input

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

Constraints

$1$

$\leq $

$N$

$\leq $

$100\, 000$

Number of products

$1$

$\leq $

$x_1, x_2$

$\leq $

$1\, 000$

Performance of a product in the tests

Output

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.

Sample Input 1 Sample Output 1
5
7 7
11 10
8 5
1 1
12 12
3 4

Please log in to submit a solution to this problem

Log in