Xəritə işarələnməsi#6845
Xəritə yaratmaq kartoqrafiyada çətin bir vəzifədir. Bu məsələnin vacib hissələrindən biri xəritədə şəhərlərin avtomatik etiketlənməsidir: hər bir şəhərin yerləşməsinə mətni olan bir etiket yapışdırılmalıdır ki, heç bir iki etiket üst-üstə düşməsin. Bu məsələdə xəritənin avtomatik etiketlənməsinin sadə bir variantını nəzərdən keçiririk.
Tutaq ki, hər bir şəhər müstəvidə nöqtə şəklindədir və onun etiketi və oxlarına paralel olan kvadratla məhdudlaşır. Hər bir şəhərin etiketi elə yerləşdirilməlidir ki, şəhər nöqtəsi etiketin yuxarı və ya aşağı tərəfinin tam ortasında yerləşsin. Yaxşı bir etiketləmədə bütün kvadrat etiketlər eyni ölçüdədir və heç bir iki etiket üst-üstə düşmür, baxmayaraq ki, onlar bir tərəfi paylaşa bilərlər. Şəkil 1 yaxşı bir etiketləmənin nümunəsini göstərir (etiket mətni göstərilmir).
Şəkil 1
Birinci sətirdə (1 \leq t \leq 10) — testlərin sayı verilir. Hər bir test (3 \leq m \leq 100) — şəhərlərin sayı olan sətir ilə başlanır. Sonra sətir gəlir, hər biri xəritədə bir şəhərin koordinatları olan iki tam ədəd — və (-10000 \leq x, y \leq 10000) verir. Heç bir iki şəhər eyni koordinatına malik deyil.
Hər bir test üçün, mümkün olan maksimum etiket ölçüsünü (tam ədəd) ayrı sətirdə yazın, yəni bu ölçüdə yaxşı etiketləmə mümkündür.
Nümunə 1