Algorithmic Truck Problem

[BBrandon]

Hello! I've been working on programming problems involving graphs, and I found an interesting one I just couldn't get an efficient program for. So the problem goes a little like this.

Consider a construction site in the shape of a coordinate grid. Multiple roads exist on lines parallel to the x-axis or y-axis. This grid of roads expands infinitely in all directions. Multiple trucks, up to 1000, are stationed a various intersections. All the trucks are described as a x and y coordinate, and each one has a unique x-coordinate and y-coordinate from the rest. All coordinates are nonnegative integers. The trucks are also positioned facing towards the north (that is, upwards on the y-axis) or facing towards the east (that is, facing to the right on the x-axis). More specifically, if a truck is positioned north and moves, it will move from (x,y) to (x,y+1). If it had instead moved east, it would have moved from (x,y) to (x+1,y).

Once a signal is given to all trucks simultaneously, they start moving in their respective direction and pour concrete behind them. If a truck ever encounters an intersection where another truck has already poured concrete, it stops. Please determine the amount of units each truck will have moved. If a truck will continue to pour concrete to infinity, print "infinity".

INPUT FORMAT:
In the first line, you are given a number N representing the total number of trucks. Following this, you are given the input of the ith truck. The input goes as follows. It starts with either the letter N or E, representing the direction the truck is orientated. Next, it will have the x-coordinate and then y-coordinate.

OUTPUT FORMAT:
Print N different lines, each with the amount of units each truck travels. If the truck does not ever stop, print "Infinity".

SAMPLE INPUT:
6
E 3 5
N 5 3
E 4 6
E 10 4
N 11 2
N 8 1
SAMPLE OUTPUT:
5
3
Infinity
Infinity
2
5

So far, I've considered how an algorithm could be created to solve this. The way I initially approached it involved sorting the trucks into the two directions. Then I sorted the North trucks by the x-coordinate and East trucks by the y-coordinate. From, here I was planning to manually iterate through each truck of each group in order. But I've had difficulties putting this into C++ code. Does anyone have any ideas how to turn this into a program, or to somehow simplify the process and make it more efficient? Additionally, are there any algorithms that may be related to this problem I should take a look at?

[JLBorges]

> If a truck ever encounters an intersection where another truck has already poured concrete, it stops.

Q. What happens if two trucks reach an intersections at the same time? Do both stop? Do both continue?

One (probably the not the most efficient way) could be:

1. create a matrix of intersections with dimensions max x, max y of the initial truck coordinates.
this matrix would hold the earliest time that a truck would reach the intersection; initialise it to hold huge values

2. iterate over the N trucks; for each truck, determine the time at which it would reach each intersection, update the earliest time matrix entry if the time is smaller. (if the time is the same as the current earliest, the answer to Q. would determine how we proceed; one possibility is we could also keep a count of number of trucks with the earliest time)

3. After the matrix has been updated in step 2, iterate over the N trucks again and compute when, if at all, it would stop.

[salem c]

Start with the simplest case possible.

5 ..E.......
4 ..........
3 ..........
2 ..........
1 .......N..
0 ..........
  0123456789

North truck is at X1,Y1 (7,1)
East truck is at X2,Y2 (2,5)

North has to move Y2-Y1 places to reach the common intersection (5-1 = 4)
East has to move X1-X2 places to reach the common intersection (7-2 = 5)

If the result is equal, then they crash.
Whichever is larger is going to get there last, and that's where it will stop.
Whichever is smaller is going to go on to infinity.
If either result is negative, then their paths never intersect to begin with (both go to infinity).

Then consider what happens when you add one more truck.

5 ..E.......
4 ..........
3 ......e...
2 ..........
1 .......N..
0 ..........
  0123456789

Move 'e' to all sorts of places to make sure you understand the problem.

Now you can develop an algorithm.

[BBrandon]

I think I should have mentioned, if both trucks reach an intersection, they both continue on.