Hide

Problem I
Blaster the Daredevil

This year, Blaster wants to make a grand exit from graduation, and what better way to do so than by launching himself out of a cannon? Blaster’s stunt can be modeled as a path in the XY-plane where the cannon is positioned at the origin, (0,0), and can be aimed at any angle.

Suspended in the air are n floating hoops, each represented as a vertical segment. The i-th hoop is located xi meters along the X-axis. The bottom of the hoop is positioned ai meters above the X-axis, and the top of the hoop is positioned bi meters above the X-axis.

Blaster, modeled as a single point, will follow a perfectly straight-line trajectory after launch (since he has conveniently disabled Earth’s gravity for this stunt). He is considered to pass through a hoop if his trajectory intersects or touches at least one point on the vertical line segment between (xi,ai) and (xi,bi).

Your task is to determine the maximum number of hoops Blaster can pass through if you carefully choose the cannon’s launch angle.

Input

The first line contains a single integer n (1n105) — the number of hoops.

Each of the next n lines contains three integers xi,ai,bi (1xi109,0aibi109), describing the position and height range of the i-th hoop.

It is guaranteed that perturbing the endpoints of hoops up or down by at most 106 meters will not affect the answer.

Output

Print a single integer—the maximum number of hoops Blaster can pass through for an optimal choice of launch angle.

Sample Input 1 Sample Output 1
5
2 1 3
4 2 5
3 1 4
5 3 6
1 2 3
4
Hide

Please log in to submit a solution to this problem

Log in