E. Labeling

The task is to place city name labels on various zoom levels of a world map.    
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.


Single line containing the SCALE number.


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


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.


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


Example output

37053 62.07982 89.99602

In this case the city is at the top left corner of the label.