LCC/Moose '19 Contest 2 S2 - Horse Race

View as PDF

Submit solution

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

Author:
Problem type

You are watching an infinite teleportational horse race with N space horses. Each horse started the race at s_i and teleports forward d_i metres every second. Unfortunately, your friend does not have the same level of enthusiasm for the sport as you. You want to impress your friend by notifying them when the most horses are passing each other! Specifically, you want to find the time and distance at which the most number of horses are incident.

Input Specification

The first line contains a single integer N.

The next N lines contain two integers, s_i, d_i indicating that the i^\text{th} horse starts the race at distance s_i and moves forward d_i metres every second.

Each horse is special and unique, so it is guaranteed that no two horses have the same (s_i, d_i) values.

Constraints

1 \le N \le 1000

1 \le s_i, d_i \le 10,000

Output Specification

Print the number of horses, time and distance for when the most number of horses are at the same time and place.

If there is a tie for number of horses, prioritize earliest time first, and then lowest distance.

The time must be after the race starts (Time must be strictly positive).

Sample Input 1

2
1 2
2 1

Sample Output 1

2 1 3

Sample Input 2

4
1 5
13 2
9 3
15 1

Sample Output 2

3 4 21

Comments

There are no comments at the moment.