Problem I. 283. (January 2012)

I. 283. In problem I. 277 proposed 2 months earlier you had to display the location and the number of inhabitants of settlements by using geographical coordinates. You are again given the same file helyforr.dat (downloadable from our webpage) containing the name (without diacritical marks), geographical coordinates and number of inhabitants of Hungarian settlements.

Create your program i283 to display the settlements and their names on the screen in a rectangle. Coordinates of this area to be displayed are specified by the user. Points representing settlements should fill up the rectangle. Names of the settlements should not overlap in the rectangle: in this case, certain names should not be displayed. Names corresponding to settlements with greater population should be displayed first. The top left corner of a box containing a name should be positioned according to the geographical coordinates of the settlement. Names can cover up points representing settlements, but not other names. A name -- at the given resolution -- should not be displayed if it overlapped another name (in the prescribed display order), or if it crossed the rectangle boundary.

Your program reads the geographical coordinates, the number of inhabitants and the name of the settlement from the above file. The first line of the file contains the number of settlements \(\displaystyle n\) together with the horizontal (\(\displaystyle dx\)) and vertical (\(\displaystyle dy\)) size of the rectangular map on the screen (\(\displaystyle 256\le dx,dy\le 1024)\). Then each of the following \(\displaystyle n\) lines contains data for the settlements. The first two pieces of data of the actual line are the longitudinal and latitudinal coordinates in minutes. The third quantity is the population, while the last piece of data is the name (without any diacritical marks).

In the first table, ``A helyforr.dat állomány tartalma'' is the content of the file helyforr.dat.

In the example, ``Bemenet a billentyűzetről'' is the input from the keyboard, ``A térkép bal felső és jobb alsó sarkának földrajzi koordinátái (egész számok)'' shows the (integer) coordinates of the top left and bottom right coordinates of the actual map, while ``Kimenet'' is the output.

The source code (i283.pas, i283.cpp, ...) together with a short documentation of your program and solution (i283.txt, i283.pdf, ...) --  also specifying the name of the developer environment to use for compiling the source file -- should be submitted in a compressed file i283.zip.

(10 pont)

Deadline expired on February 10, 2012.

Sorry, the solution is available only in Hungarian. Google translation

Megoldásokról:

A feladat előzményének tekinthetjük az I.277-es, település lélekszám alapján történő térkép és az I.274 legnagyobb szabad téglalap keresési feladatot. Több jó megoldás érkezett. 1-1 pontot vesztett, aki az ábrázolandó tartományhoz a földrajzi koordináták beolvasásánál felirattal nem segítette a felhasználót, illetve a dokumentációban nem írt a megoldás rövid algoritmusáról.

Gema Barnabás 11. osztályos (Veszprém, Lovassy László Gimnázium) leírásából:

Elsőként a programom megnyitja a helyforr.dat fájlt, majd beolvassa belőle az adatokat. A városok adatait eltárolja egy rekord típusú tömbben. Ezután bekéri az ábrázolási téglalap koordinátáit és egy új tömbbe kigyűjti a téglalapba eső városok rekordjait és rendezi őket lakosság szerint csökkenően.

Ezután következik az ábrázolás. A program gyakorlatilag csak egy hasonlósági transzformációt végez el a koordinátákon és településeket ábrázolja egy képponttal. A képpont a település tényleges koordinátájától 2 képponttal északra és 2-vel nyugatra tolódik, hogy tényleges koordinátán kezdődhessen a felirat és a pontot is lehessen látni. A pontok után a feliratok következnek, amiknek kiterjedésének megállapításához a TextWidth és a TextHeight függvényeket használtam fel. Először a program megállapítja, hogy kilógna-e a felirat az ábrázolási téglalapból, és ha nem, akkor azt is ellenőrzi, hogy nem érne-e rá egy másik feliratra. Ehhez létrehoztam egy mátrixot, ami azt tárolja, hogy egy képpont fel lett-e már használva. Ha egy feliratot sikerül kiírni, akkor az lefoglalja a saját területét a mátrixban.

A tömb rendezése a feliratok kiírásához volt szükséges, mivel így a nagyobb lélekszámú települések neve kerül előbb kiírásra.

Mintamegoldásként Beleznay Soma 10. osztályos (Budapest, Fazekas Mihály Fővárosi Gyakorló Gimnázium) tanuló munkáját közöljük: i283.pas

Kucsma Levente István 9. osztályos (Eger, Dobó István Gimnázium) programjának eredménye:

Statistics:

10 students sent a solution.
10 points:	Beleznay Soma, Fényes Balázs, Gema Barnabás, Jákli Aida Karolina, Kovács Balázs Marcell, Kucsma Levente István, Szabó Levente.
9 points:	Antal János Benjamin, Barkaszi Richárd Miklós, Veress Péter.

Problems in Information Technology of KöMaL, January 2012