Скрито съкровище

Задача #4 от конкурса на PC Magazine Bulgaria и Telerik, сезон 2011/2012

Кръг на Технологика

Търсене на скрито съкровище

Легендата разказва, че високо в планината е заровено съкровище. Единствената следа към местоположението на скритото богатство представлява лошо съхранявана старинна топографска карта. На нея се различават единствено единични точки от хоризонтали, описващи релефа, и надпис, че съкровището е отбелязано с точка и е заровено в иглата на върха (най-високото място от местността).  Хоризонталът представлява непрекъсната затворена крива линия, която условно изобразява точки с еднаква надморска височина. Известен археолог ни моли за съдействие при възстановяването на картата.  Разказва ни, че картата изобразява хоризонталите само на един от планинските върхове и че всички върхове в тази област са конусовидни, без прорязващи долини и отвесни стени.

На фигура 1 и фигура 2 са показани примерна карта и нейна реставрация, като съкровището е маркирано с червен знак.

Фигура 1: Оригинална карта

Фигура 2: Реставрирана карта

Алгоритмична задача: Търсене на скрито съкровище

Вашата задача е да измислите и реализирате алгоритъм, който намира местоположението на скритото съкровище за минимално време. Считаме, че хоризонталите са изпъкнали многоъгълници. Всеки две съседни страни от многоъгълник  сключват ъгъл по-малък от 180 градуса.  Многоъгълниците  се влагат един в друг, без да се допират или пресичат. Върхът е единствената точка, която се намира в най-вътрешния многоъгълник и не лежи на него.

Входни данни

Входните данни се четат от файл с име map.in намиращ се в текущата директория на стартиране на програмата. На първия ред има цяло положително число N, което задава броя на точките отбелязани върху картата. На втория ред са зададени координатите на точките (четен брой числа по двойки дават X и Y), като:

• няма повтарящи се точки;
• точките имат целочислени координати (X Y), записани с разделител интервал;
• разделителят между две точки е интервал.

Изходни данни

Резултатът от работата на програмата трябва да бъде изведен в текстови файл с име map.out, намиращ се в текущата директория на стартиране на програмата. Той трябва да съдържа:

• Две цели числа разделени с интервал, отговарящи на координатите на съкровището;
• ERR, когато е нарушен форматът на входния файл;
• NO, когато форматът на входния файл е верен, но картата е невярна (няма единствена точка в най-вътрешния многоъгълник или два многоъгълника имат обща точка).
• Броят на точките N е цяло положително число в диапазона [3; 100 000]
• Координатите на точките X и Y са цели числа в диапазона [-1 000 000; 1 000 000]

Ограничения

Примери:

Вход	Изход	Коментар
31 3 -1 2	ERR	Не са подадени посочения брой точки
3-1 1 1 6 3 7	NO	Няма вътрешна точка за хоризонталата
61 1 1 3 1 6 3 7 2 5 1 5	NO	Има допиращи се многоъгълници
41 1 3 7 1 6 2 5	2 5	Намерено съкровище

Задача по приложно програмиране: GUI за визуализация на карта на съкровище

Да се разработи цялостно приложение с потребителски интерфейс за визуализация на карта на съкровище. Приложението може да бъде настолно или уеб базирано. То трябва да поддържа следната функционалност:

• Зареждане на входен файл, описващ скрито съкровище;
• Запазване в изходен файл координатите на съкровището;
• Визуализация на карта на съкровище, съдържаща хоризонтали, описващи релефа на местността, и маркирано местоположение на съкровището;
• Редакция на входните точки (добавяне, изтриване, местене).

Критерии за оценяване

Оценяването на предложените от участниците в конкурса решения на алгоритмичната и приложната задача ще се извърши от специализирано жури по критериите, описани по-долу. Всяко решение, предадено от участник в конкурса (индивидуален състезател или екип), ще получи до 20 точки в зависимост от оценките, получени по отделните критерии. Възможно е предаване само на алгоритмичната част или на алгоритмичната + приложната част на задачата, като липсващата част се оценява с 0 точки.

Алгоритмична задача – критерии за оценяване

Оценяването се извършва с тестове. Резултатът за дадено решение представлява сумата от времето за изпълнение на всеки един от тестовете. За всеки тест ще бъде определено максимално допустимо време. Общото максимално допустимо време представлява сумата от максимално допустимите времена за всеки един тест. При некоректен резултат – невярно посочено местоположение на съкровището, посочване на изход NO или ERR при съществуващо решение, посочване на точка при очакван изход NO или ERR, посочване на изход NO при очакван изход ERR (съответно изход ERR при очакван изход NO), както и при превишаване на определеното време за работа, към времето на решението се добавя максимално допустимото време за конкретния тест. Решения, които не се вместват в определеното общо максимално допустимо време, получават 0 точки.  10 точки  получава най-бързото решение. Останалите решения  взимат пропорционално точки спрямо него. Точките се закръглят до цяло число.

Приложна задача – критерии за оценяване

Допълнителни изисквания

Задачите позволяват използването на различни езици за програмиране и технологии (например PHP, C, C++, C#, Delphi, Python, WPF, XAML, Windows Forms, Java, Swing, Flash, JavaScript, HTML5). Всички предадени решения ще бъдат тествани в Windows среда съгласно общите условия на конкурса.

За алгоритмичната част се изисква да бъде предаден пълният сорс код + изпълним файл за Windows (.exe). Ако програмирате на език, който по природа не създава изпълними .exe файлове (например PHP, Python, Java или JavaScript), предайте само сорс кода.

За приложната част се изисква да бъде предаден пълен сорс код + изпълним .exe файл (когато е възможно). При уеб приложения (например на PHP, Python, ASP.NET, Java EE или JavaScript) предайте техния код + кратки инструкции за настройка и стартиране.

Анализ на четвърти кръг и резултати

В този кръг предизвикахме състезателите да търсят скрито съкровище. Заслугите за добрата задача са на Технологика, по-голямата част от оценяването се извърши от същите. Няколко отбора „търсачи на съкровища“ предадоха решения на задачата, като едно от тях стана неоспорван лидер в класирането. Интересно е да се отбележи, че всички участници се бяха постарали повече за приложната, отколкото за алгоритмичната част на своите решения. Сигурно за този феномен обяснението не е сложно – несъмнено, много хора биха се зарадвали на приложението на програма, която намира съкровища. Както обикновено, резултатите са на края на тази статия (така че нетърпеливите могат да погледнат надолу).

За оценяването и резултатите от алгоритмичната част

Оценяването на алгоритмичната част беше проведено по стандартния начин – всеки алгоритъм бе изпитан чрез поредица от тестове. За радост на оценяващите, алгоритмите в този кръг се справяха добре с описаният формат на входните и изходните данни.

Технологика предостави сериозно количество тестови случаи, с които да се изпита коректността на решенията. С няколко думи – имаше всички възможни сценарии – от голямо количество входни данни, през сложни конфигурации, до некоректно зададени входни данни или некоректни карти (с които се цели да се изпита справянето на алгоритмите с такива ситуации).

Естествено, тестването беше автоматизирано и проведено на същата машина, която беше ползвана за тествана на решенията на предишните кръгове. Отчетохме времето за работа на всеки алгоритъм и тази информация беше използвана при изготвянето на резултатите.

Един от алгоритмите се представи значително по-добре от останалите и съответно получи максималният брой точки за тази част, а останалите получиха съответно част от тези точки.

За оценяването и резултатите от приложната част

Както беше споменато по-горе, по-високи резултати решенията получиха в приложната част. Оценяването се извърши от екип на Технологика, който оцени приложенията по споменатите в условието на задачата критерии – коректност на работа, ползваемост, дизайн, устойчивост на грешки и оригиналност.

Отново, в тази част имаме убедителен лидер, който получи близки до максималните точки за тази част.

Крайни резултати

Това е класирането базирано на крайните резултати от четвърти кръг на състезанието, образувани от сбора на точките от алгоритмичните и приложните части, предадени от състезателите. Поздравления на всички за резултатите! Благодарим Ви за участието!

 

Отбор	Краен резултат	Алгоритъм	Приложение
Тони Ганчев	18	8	10
Димитър Дилянов Иванов	3	0	3
Mарио Стоилов и Ивайло Кирилов	2	1	1