7968: USACO 2018 February Contest, Platinum —— Problem 1. Slingshot
[Creator : ]
Description
One of the farming chores Farmer John dislikes the most is hauling around lots of cow manure. In order to streamline this process, he comes up with an intriguing idea: instead of hauling manure between two points in a cart behind his tractor, why not shoot it through the air with a giant manure slingshot? (indeed, what could possibly go wrong...)
Farmer John's farm is built along a single long straight road, so any location on his farm can be described simply using its position along this road (effectively a point on the number line). FJ builds N slingshots ($1≤N≤10^5$), where the i-th slingshot is described by three integers $x_i, y_i, t_i$, specifying that this slingshot can shoot manure from position $x_i$ to position $y_i$ in only $t_i$ total units of time.
FJ has M piles of manure to transport ($1≤M≤10^5$). The j-th such pile needs to be moved from position $a_j$ to position $b_j$. Hauling manure with the tractor for a distance of d takes d units of time. FJ is hoping to reduce this by allowing up to one use of any slingshot for transporting each pile of manure. Time FJ spends moving his tractor without manure in it does not count.
For each of the M manure piles, please help FJ determine the minimum possible transportation time, given that FJ can use up to one slingshot during the process.
FJ has M piles of manure to transport ($1≤M≤10^5$). The j-th such pile needs to be moved from position $a_j$ to position $b_j$. Hauling manure with the tractor for a distance of d takes d units of time. FJ is hoping to reduce this by allowing up to one use of any slingshot for transporting each pile of manure. Time FJ spends moving his tractor without manure in it does not count.
For each of the M manure piles, please help FJ determine the minimum possible transportation time, given that FJ can use up to one slingshot during the process.
Input
The first line of input contains N and M.
The next N lines each describe a single slingshot in terms of integers $x_i, y_i, t_i\ (0≤x_i,y_i,t_i≤10^9)$.
The final M lines describe piles of manure that need to be moved, in terms of integers $a_j$ and $b_j$.
The next N lines each describe a single slingshot in terms of integers $x_i, y_i, t_i\ (0≤x_i,y_i,t_i≤10^9)$.
The final M lines describe piles of manure that need to be moved, in terms of integers $a_j$ and $b_j$.
Output
Print M lines of output, one for each manure pile, indicating the minimum time needed to transport it.
Sample 1 Input
2 3
0 10 1
13 8 2
1 12
5 2
20 7
Sample 1 Output
4
3
10
Here, the first pile of manure needs to move from position 1 to position 12. Without using an slingshot, this would take 11 units of time. However, using the first slingshot, it takes 1 unit of time to move to position 0 (the slingshot source), 1 unit of time to fling the manure through the air to land at position 10 (the slingshot destination), and then 2 units of time to move the manure to position 12. The second pile of manure is best moved without any slingshot, and the third pile of manure should be moved using the second slingshot.