Abednego wrote:I probably have some stupid typo in my program, but could anyone please clarify what this means?
Code: Select all
The destinataries of a station are the two closest stations. In case of draw, the first criterion is to chose the westernmost (leftmost on the map), and the second criterion is to chose the southernmost (lowest on the map).
It means - from each node, there are atmost two edges. These two edges connect the the first node to two closest nodes.Suppose there are 3 nodes at a given minimum distance `d' from U.Now U will have edges to
1. V ( where Vx < min(Wx, Tx) ), V,W & T are equidistant from U
2. V' ( where V'y < min(W'y, T'y) ), V',W' & T' are equidistant from U
This is my understanding:
1. For each station U, sort all other stations by distance to U.
2. In case of a tie, sort by smallest X-coordinate.
3. In case of a tie, sort by smallest Y-coordinate.
4. Make the first 2 stations U's neighbours in the directed graph.
5. Run DFS/BFS from U and make sure each vertex is reachable.
(I know that I need something smarter to avoid TLE, but this is the main idea.)
Is this correct? The problem never says what the X and Y coordinates correspond to in terms of left/right/up/down/N/S/E/W. Also, could there be several stations with the same XY-coordinates?
Thanks.
I am doing more or less the same thing.But the only difference is I am creating a graph that satisfies the given constraint.In your algo, it appears the constraint is satisfied for the starting vertex only(step 4).I may be wrong, of course.
And I used DFS(the same algo found in CLR), so dont worry, you dont need to go overboard.And I used EPSILON=1e-6.
One small hint:
the only method in my program that is longer than 12 lines is the create-graph() routine
