LCC/Moose '18 Contest 3 J5 - Line Intersections

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

Max has just started grade 9, and he is in his math class, learning equations of lines!

Max defines the slope-intercept form of a line as the equation of the line in the form y = mx + b. Max is given N lines in slope-intercept form, each with a distinct m and b. Max wants to see, at some integer x, the maximum possible y value out of all the N lines. He wants to test all integer values of x in the range [1,10^5], and wants the sum of these y values.

Not knowing how to do it, he has asked you to do it for him! Help him!

Input Specification

The first line will contain the integer N (1 \le N \le 10^5), the number of lines.

The next N lines will each contain two integers, m, b (-10^6 \le m, b \le 10^6). It is guaranteed both m and b are distinct.

Output Specification

On the first line, output the sum of the maximum possible y values for every integer x in the range [1, 10^5]. Note that 64-bit integers may be required to pass.


Subtask 1 [40%]

N \le 10

Subtask 2 [60%]

No further constraints.

Sample Input 1

4 2
-4 -6
0 -2

Sample Output 1


Sample Input 2

-1 1000
1 -1000

Sample Output 2



There are no comments at the moment.