Navngivning på kort

Du er assistent for en kartograf og er blevet tildelt den svære opgave at skrive bynavnene på et nyt kort.

Kortet består af 1000 gange 1000 felter. Hver by fylder præcis eet felt på kortet. Bynavne skal placeres på kortet i en rektangulær boks. En sådan boks kaldes en etiket.

Fig. 1: En by med de fire mulige placeringer af dens etiket

Placeringen af etiketter skal opfylde følgende krav:

En bys etiket kan optræde i een af fire mulige positioner i forhold til byens placering (se figur 1).
Etiketter må ikke dække over hinanden.
Etiketter må ikke dække over byer.
Etiketter må ikke gå ud over kortets kant.

Enhver etiket skal indeholde alle bogstaverne fra bynavnet plus et enkelt mellemrumstegn. For hvert bynavn er givet bredden og højden for dets bogstaver, og et mellemrum har den samme størrelse. En del af et kort

repræsenterer et mellemrumstegn

repræsenterer positionen af en by Fig. 2: En del af et kort

Rækker og søjler på kortet er nummereret således at felterne længst til venstre har søjlenummer 0 og så de nederste felter har rækkenummeret 0. På figur 2 vises et udsnit af det nederste venstre hjørne af et kort, med byerne Langa i (0, 3), Ceres i (6,1) og Paarl i (7,3). Alle etiketterne er placeret korrekt, men den viste placering er ikke den eneste mulige.

Opgave

Du skal skrive et program, der indlæser byernes placering, deres bogstavstørrelse og navn, for derefter at placere så mange etiketter som muligt, idet de ovenfor nævnte krav skal overholdes. Positionen af de placerede etiketter skal skrives til output-filen.

Input

På første linje i input-filen står heltallet N , som angiver antallet af byer på kortet. På de næste N linjer følger data for de enkelte byer. Data for en by består af

byens søjlenummer (X)
byens rækkenummer (Y)
bogstavbredden (W) for bogstaverne i bynavnet
bogstavhøjden (H) for bogstaverne i bynavnet
bynavnet

Antallet af byer kan højst være 1000. Et bynavn er et enkelt ord og kan højst have 200 bogstaver.

Eksempel på input

MAPS.DAT	Forklaring
3	N=3
0 3 1 1 Langa	X=0, Y=3, W=1, H=1
6 1 1 1 Ceres
7 3 1 2 Paarl

Output

Programmet skal til output-filen skrive N linjer, een for hver by. Hver linje består af søjlenummeret og rækkenummeret for øverste venstre hjørne for byens etiket. Hvis programmet ikke er i stand til at placere en bys etiket, skal placeringen angives som –1 –1 .

Linjerne skal skrives i samme rækkefølge som byerne forekommer i input-filen. De to tal skal adskilles af et enkelt mellemrum.

Eksempel på output

MAPS.OUT	Forklaring:
1 4	Langa’s etiket starter i (1,4)
0 0	Ceres’s etiket starter i (0,0)
8 2	Paarl’s etiket starter i (8,2)

Pointberegningen

For hvert sæt af testdata gælder:

Pointene beregnes som den procentdel af bynavnene, programmet har placeret, i forhold til det antal, arrangørernes program kan placere.
Der kan højst gives 100 og mindst 0 point.
Hvis en etiket ikke overholder kravene gives 0 point.
Hvis etiketternes rækkefølge i MAPS.OUT ikke svarer til de tilsvarende bynavnes i MAPS.DAT, gives 0 point.