Maximum Level Archery Challenge

In this problem, a 2D archery game is played by shooting an arrow from the origin \((0,0)\) with an adjustable angle \(\theta\) (in the interval \((0, 90^\circ)\)) and any positive speed. The arrow is a beam of light with penetration ability so that if its parabolic trajectory touches a target, that target is considered hit.

The targets are vertical line segments in the first quadrant, not touching any axes, and no two targets overlap or touch each other. In the challenge mode, the game starts with one target in level 1. At level 2 a new target is added; to pass level 2, one must shoot an arrow that passes through both targets. At level \(K\), there are \(K\) targets; passing this level requires one shot hitting all \(K\) targets simultaneously. If a shot does not hit all targets, the game ends. Given the positions of the targets that appear in each level, your task is to determine the maximum level that can be passed.

The projectile motion of the arrow (ignoring air resistance) follows the standard equations. When an arrow is shot with an initial speed \(v\) and angle \(\theta\), the position at time \(t\) is:

[ x = v\cos\theta,t, \quad y = v\sin\theta,t - \frac{1}{2}g t^2, ]

When the arrow crosses the vertical line at \(x=x_i\) (the location of a target), the time is \(t = \frac{x_i}{v\cos\theta}\) and the height is given by:

[ y_i = x_i\tan\theta - \frac{g x_i^2}{2v^2\cos^2\theta}. ]

Each target \(i\) is described by its fixed \(x_i\) coordinate and its vertical span \([L_i, R_i]\) (endpoints included). A target is hit if the arrow's trajectory at \(x=x_i\) is within \([L_i, R_i]\). For a fixed angle \(\theta\), note that as \(v\) increases, \(y_i\) approaches \(x_i \tan \theta\) from below. Thus, for target \(i\) to be achievable, it is necessary that:

[ x_i\tan\theta \ge L_i. \quad (1) ]

In fact, if \(x_i\tan\theta \le R_i\) for all \(i\), one may choose \(v\) sufficiently large so that \(y_i\) gets arbitrarily close to \(x_i \tan\theta\), thereby hitting each target. Therefore, a sufficient and necessary condition for the existence of a shot that hits a given set of targets is that there exists an angle \(\theta\) such that for every target \(i\):

[ L_i \le x_i\tan\theta < R_i. \quad (\text{note that if }x_i\tan\theta = R_i, \text{ one can still adjust }v \text{ to touch }R_i) ]

This condition can be reformulated as finding a \(\theta\) for which:

[ \tan\theta \in \bigcap_{i=1}^K \left[\frac{L_i}{x_i}, \frac{R_i}{x_i}\right]. ]

Since \(\tan\theta\) can be any positive real number (by choosing \(\theta\) in \((0, 90^\circ)\)), the feasibility reduces to checking whether:

[ \max_{1\le i \le K}\left(\frac{L_i}{x_i}\right) < \min_{1\le i \le K}\left(\frac{R_i}{x_i}\right). ]

Your task is to determine the maximum level \(K\) (starting from level 1) such that the above intersection is nonempty. The targets are given in the order they appear in the game (i.e. level 1, level 2, …).

inputFormat

The first line contains an integer \(N\) (the number of targets/levels). Each of the following \(N\) lines contains three real numbers \(x\), \(L\) and \(R\) describing a target. Here, \(x\) (\(> 0\)) is the \(x\)-coordinate of the target, and \([L, R]\) (with \(0 < L < R\)) represents the vertical span of the target.

outputFormat

Output a single integer representing the maximum level that can be passed with one shot hitting all targets from level 1 up to that level.

sample

1
1 1 2

1

</p>