XIII конкурс по програмиране на PC Magazine Bulgaria и Мусала Софт

В този брой на сп. PC Magazine Bulgaria стартира четвъртият кръг от тринадесетото издание на най-елитния частен конкурс по програмиране в страната, организиран съвместно от списанието и фирма Мусала Софт. Задачите в кръговете ще продължат да са от алгоритмичен и практико-приложен характер, като същевременно сме се постарали да предложим приятни изненади на състезателите и да им осигурим все по-вълнуващи награди. В този кръг на конкурса наградите са осигурени от фирма iFAO. Задачата е подготвена от Борис Караджов, iFAO.

Глобус

В Голямата гора настана нова мода. Всички сега прекарват по цял ден пред новата игра – Empire Globe. Манията е достигнала такъв мащаб, че ежедневно се организират турнири и са се сформирали множество кланове от играчи, борещи се за надмощие.

Мечо Пух не иска да изостава и от доста време се опитва да се присъедини към клана [HоPо] (от Honey Pot), в който са вече Прасчо и Тигър. За разлика от тях обаче Мечо не е толкова добър в играта, защото си е продал компютъра, за да си купи мед, и не е тренирал.

Empire Globe е последно поколение масова онлайн космическа икономическа походова ролева стратегия от първо лице. Всеки си има държава, заемаща цяла планета със сферична форма, на която са изградени няколко града. Икономическият аспект в играта, който особено много затруднява Мечо, изисква градовете да бъдат разпределени на области. За целта някои градове се избират за областни центрове. Въвеждат се и сфери на влияние на областните центрове, които имат еднакъв радиус, за да няма ощетени. Град, който влиза в дадена сфера на влияние, става част от съответната област.Разбира се, всяко селище трябва да се намира в точно една област.

Политическата система в Empire Globe е доста сложна. Управлението на множество области е много трудна работа, затова всяко разбиване на по-малко на брой области е по-добро от такова на повече. Въпреки това градовете трябва да са разделени поне на две, защото в противен случай единствената област ще съвпадне с цялата държава и ще създаде предпоставки за бунтове и преврати. Разстоянията също са трудност за успешно управление, затова е желателно радиусът на областите да е минимален.

Вход

На първия ред на входния файл GLOBE. INP ще получите числото N (1<1000), означаващо броя на градовете. На всеки от следващите N реда ще получите две дробни числа с един знак след десетичния разделител, описващи позицията на съответния град върху планетата посредством географска ширина в интервала [-90, 90] и дължина в интервала (-180, 180]. Няма градове, намиращи се на едно и също място.

Изход

В изходния файл GLOBE.OUT трябва да опишете намереното разбиване. На първия ред трябва да изпишете броя на областите. След това за всяка област да има изписан по един ред, съдържащ номерата на всички градове, които влизат в нея, започвайки от центъра. Градовете са номерирани с естествените числа от 1 до N, нарастващи по реда, по който се намират във входния файл.

Оценяване

Ако програмата не създаде правилно разбиване или не успее да завърши за 10 секунди, ще получи нула точки на съответния тест. В останалите случаи точките ще бъдат изчислявани относително. Първо за разбиването на всеки участник се изчислява коефициентът , където K е броят на областите, а R е радиусът на влияние, разделен на радиуса на глобуса. Намира се най-малкият коефициент mP и всеки участник получава от точките за съответния тест. При оценяване се избира минималният радиус за предложеното разбиване на области.

Решенията на задачата може да изпратите чрез системата за upload директно на сайта http://konkurs.musala.com до 11 февруари 2008 г.

Примерен GLOBE.INP:

Примерен GLOBE.OUT