Description

Momo is playing a 2D archery game, as shown in Figure 1. In this game, the x-axis lies on the ground, and in the first quadrant there are several vertical segments serving as targets. Any two targets are disjoint, and none of them touch the coordinate axes.

Momo controls an archer located at $(0, 0)$. She can shoot an arrow of light with piercing ability at any angle between 0 and 90 degrees (excluding 0 degrees and 90 degrees), with any power. Since there is no air resistance in the game and the arrow of light has no shaft, the trajectory is a standard parabola. All targets crossed by the trajectory are considered hit, including those whose endpoints are hit only.

This game has multiple modes, and Momo’s favorite is the challenge mode.

In challenge mode, the first level has only one target. Hitting this target allows her to enter level two, where one more target appears in addition to the first one. If she can hit both targets with a single shot, she can enter level three, where a third target appears. And so on: at each level, a new target appears. At level $K$, she must hit all $K$ targets that have appeared in the first $K$ levels with a single shot to enter level $K+1$; otherwise, the game ends.

Momo has spent a lot of time on this game, but she can only reach level seven, “Seven Stars in a Row,” which confuses her. She has obtained the positions of the targets that appear in each level and wants you to tell her the maximum number of levels she can pass.

Input Format

The first line of input contains a positive integer $N$, indicating that there are $N$ levels.

The next $N$ lines follow. Line $i+1$ contains three positive integers $x_i, y_{i1}, y_{i2}\ (y_{i1}<y_{i2})$, meaning that in level $i$ the target’s x-coordinate is $x_i$, and its y-range is from $y_{i1}$ to $y_{i2}$.

Output Format

Output a single integer, the maximum number of levels that can be cleared.

5
2  8 12
5  4 5
3  8 10
6  2 3
1  3 7

3

Hint

Constraints:

• 30% of the testdata satisfy $N \le 100$.
• 50% of the testdata satisfy $N \le 5000$.
• 100% of the testdata satisfy $N \le 100000$, and all given coordinates do not exceed $10^9$.

Translated by ChatGPT 5