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,
Suspended in the air are
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
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
Each of the next
It is guaranteed that perturbing the endpoints of hoops up
or down by at most
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 |