Description

A country has developed a missile interception system to defend against incoming enemy missiles. However, this system has a flaw: although the first shell can reach any height and intercept a missile of any speed, each subsequent shell cannot exceed the height of the previous one, and the speed of the missile it intercepts cannot exceed that of the previous one. One day, the radar detects an incoming enemy missile attack. Since the system is still in trial use, there is only one set available, so it may not be able to intercept all missiles.

If not all missiles can be intercepted, we certainly want to minimize losses, that is, choose a plan that intercepts the maximum number of missiles. However, there may be multiple optimal plans that intercept the maximum number of missiles. If there are multiple optimal plans, we will choose one uniformly at random as the final interception plan.

Our spies have obtained the height and speed of every enemy missile. Your task is to compute, under the decision process described above, the probability that each missile is intercepted.

Input Format

The first line contains a positive integer $n$, the number of enemy missiles.

The next $n$ lines give all missiles in order. The $(i+1)$-th line contains two positive integers $h_i$ and $v_i$, denoting the height and speed of the $i$-th missile.

Output Format

Output two lines.

The first line contains a single positive integer, the maximum number of missiles that can be intercepted.

The second line contains $n$ real numbers between $0$ and $1$, where the $i$-th number is the probability that the $i$-th missile is intercepted (you may keep any number of significant digits).

4
3 30
4 40
6 60
3 30

2
0.33333 0.33333 0.33333 1.00000

Hint

The total number of optimal plans does not exceed the storage range of C++ double.

Constraints

• Approximately $30\%$ of the testdata have all $v_i$ equal.
• Approximately $50\%$ of the testdata satisfy $1 \le h_i, v_i \le 1000$.
• For $30\%$ of the testdata, $1 \le n \le 1000$.
• For $100\%$ of the testdata, $1 \le n \le 5 \times 10^4$, $1 \le h_i, v_i \le 10^9$.

Scoring

• For each test point, if the first line of your output matches the standard answer, you receive $40\%$ of the score for that test point.
• If, in addition, every number on the second line has an absolute error no greater than $10^{-4}$ compared to the standard answer, you receive the remaining $60\%$.

Translated by ChatGPT 5