CCO Preparation Test 3 P3 - Arrow

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 0.6s
Memory limit: 128M

Problem types

Bruce is playing the game Green Arrow. In the game, the ground is the x-axis and the targets are a number of vertical line segments in the first quadrant. There is no intersection between any two targets. Moreover, no target touches the x-axis. Bruce can control a game character, always located at (0, 0), to shoot an arrow towards the first quadrant with an angle \theta (0^\circ < \theta < 90^\circ). There is no air resistance in the game. Thus, the trajectory of the arrow will be a standard parabola. The targets which are crossed by the trajectory are hit in the game, including those with only endpoints crossed by the trajectory.

In challenge mode, there are a number of rounds. In the first round, there is only one target. If Bruce hits the target, he can pass to the second round. In the second round, the target in the first round will appear and a new target will be added. Bruce has to hit both of the targets, so that he can pass to the next round. Similarly, in the k-th round, the targets in the previous k-1 rounds will appear and a new target is added. Bruce can pass to the next round only if he can make a shot to hit all targets in this round. Bruce has hacked the game and gets the locations of all targets. He wants to know the maximum number of rounds he can successfully pass. It is possible that Bruce can win the game, in which case there are no more rounds to pass after that.

Input Specification

The first line of input will consist of one integer, N (1 \leq N \leq 100\,000), the number of rounds in the game. Each of the following N lines will consist of three integers, x_i (0 < x_i < 10^9), y_{i1}, and y_{i2} (0 < y_{i1} < y_{i2} < 10^9), which are the target i's horizontal position, the low endpoint, and the high endpoint, respectively.

Output Specification

Output one integer, the maximum number of rounds Bruce can pass.

Sample Input

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

Sample Output


Explanation of Output for Sample Input

The sample case is as shown in the following figure.


There are no comments at the moment.