E. Labeling
| The task is to place city name labels on various zoom levels of a world map. | 
|
A list of cities with name, location and population is given in a tab separated
file, cities.txt, the description of the columns is in the
cities.readme file.
The label is written on the map using a 6x10 unit fixed width font, so it covers a rectangular area which height is 10 units and width is 6 units times the number of characters in the name of the city.
A label should be placed right next to its city and labels must not overlap.
The coordinates of a geographic location on the map is given by
x = longitude * SCALE y = latitude * SCALE
where longitude and latitude are in degrees as in cities.txt
and x, y are in the same units as the font of the labels.
The map wraps around horizontally so a label truncated on the right continues on the left side of the map. Vertically labels must not get truncated.
People are happy when they see the label of their city displayed on the map and you want to make as many people happy as possible.
Input
Single line containing the SCALE number.
Output
Each line of the output must contain three numbers separated by whitespace:
ID,X,Y.
Where ID is the id of a city (first column in cities.txt),
and X,Y are the coordinates of the
center of the label of the city (in map coordinate system).
Labels may appear in arbitrary order in the output and you don't have to label every city.
The location of a city must be on the boundary of its label and labels must not overlap, these constraints will be checked with 0.1 unit precision.
The map is cylindrical and the coordinate system wraps around horizontally:
X+360*SCALE,Y is the same point as X,Y.
When printing the coordinates of a label make sure that
-180 * SCALE <= X <= 180 * SCALE -90 * SCALE + 5 <= Y <= 90 * SCALE - 5
Score
P = sum(population of labelled cities) SCORE = 100 * (1 - sqrt(1 - P/MAXP))where
MAXP is the best P submitted so far.
Note that a rendered map with the best labeling will be published at http://ch24.org/ec/labeling during the contest.
cities.txt
Example lines from cities.txt
... 37051 HU Budakeszi 47.51667 18.93333 13248 37052 HU Budaors 47.46181 18.95845 25089 37053 HU Budapest 47.49801 19.03991 1696128 37054 HU Bugac 46.68889 19.67944 3066 37055 HU Bugyi 47.21667 19.15 5412 ...
Example input
2.0
Example output
37053 62.07982 89.99602
In this case the city is at the top left corner of the label.