Problem I. 388. (December 2015)
I. 388. It is only since a few centuries that maps have been oriented in a way such that north is put on top. Earlier, various other directions were chosen to be put on top, depending on the cultural environment. Some Egyptian maps, for example, used the flow direction of the Nile river; American settlers used maps with west on top (the direction they were often heading); and in Europe, they put north on top.
In this exercise all maps are oriented according to one of the four cardinal directions. The maps were made to serve different purposes, and they have different cardinal points. By knowing the coordinates of these points, you need to determine the map orientation. The location of the origin can vary from map to map.
The first line of the input file (terkep.be) contains the number of maps (\(\displaystyle T\le 50\)), a space character as a separator, and the orientation of the first map (E, K, D, N, denoting north, east, south and west, respectively). Then each of the next \(\displaystyle T\) lines contains the following information. The first number is the number of points (\(\displaystyle N\)) on the given map; then there are \(\displaystyle N\) triplets: the first number in each triplet is the identification number of the actual point, then its \(\displaystyle X\) and \(\displaystyle Y\) coordinates (relative to the given map) appear. Each piece of data is separated by a space character. The total number of points is at most 50. The coordinate values lie in the interval \(\displaystyle [-1000; 1000]\) for a given orientation, however, by taking the union of some maps, this interval may become wider.
The output file (terkep.ki) should have exactly \(\displaystyle N\) lines; each line should have one character, the orientation of the actual map. If the orientation cannot be determined, a character X should be present in that line.
The source code and documentation of your program-containing a brief description of your solution, and the name of the developer environment to compile your code-should be submitted in a compressed file i388.zip.
Deadline expired on 11 January 2016.