Cheerio Contest 1 S3 - Stock Trading

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types

Ethan is an avid stock trader. In order to predict future stock prices, he performs technical analysis on stock charts by drawing trendlines. The chart is displayed as a grid with time on the x-axis and price on the y-axis. There are N points, where the i^\text{th} point is (t_i, p_i), indicating that at time t_i, the stock price was p_i. Adjacent points are then connected to form a line graph. That is, point i is connected to points i-1 and i+1.

The line connecting two points (t_i, p_i) and (t_j, p_j) where j > i is considered to be a trendline when all points in the range [i, j] are either all above/on the line or all below/on the line. Can you help Ethan find the number of different trendlines he can draw? Two trendlines are considered different if they start or end at different points.


For all subtasks:

  • t_1 < t_2 < t_3 < \dots < t_N
Points Awarded N t_i, p_i
5 points 2 \le N \le 300 0 \le t_i, p_i \le 10^4
6 points 2 \le N \le 5\,000 0 \le t_i, p_i \le 10^4
4 points 2 \le N \le 5\,000 0 \le t_i, p_i \le 10^9

Input Specification

The first line contains one integer N.

The next N lines contain two integers t_i and p_i.

Output Specification

Output the number of different trendlines that could be drawn.

Sample Input

0 0
2 4
5 2
6 5

Sample Output


Explanation for Sample Output

Notice that the line connecting points 1 and 4 is not a trendline.


There are no comments at the moment.