[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Задача Барок 2  XML
Forum Index » Задачи од национални натпревари
Author Message
Scratcher



Joined: 21/01/2013 16:53:12
Messages: 14
Offline

http://mendo.mk/Task.do?id=466

Дали има некој идеја за решение на задачата?

Досега стигнав до ова решение кое поминува само на првите 6 тест случаеви
а на останатите вади runtime error(претпоставувам заради матрицата city)
Perez



Joined: 18/10/2014 18:53:59
Messages: 93
Offline

Користи Debugger, ќе ти помогне да го најдеш Runtime Errorot
Scratcher



Joined: 21/01/2013 16:53:12
Messages: 14
Offline

@Perez

Благодарам за одговорот.

Инаку, проверив дека причината за runtime error-от е тоа што неможе да се иницијализира матрица [750000][750000]

Значи, останува да се најди сосема друго решение.

Ти ја имаш решено?
Perez



Joined: 18/10/2014 18:53:59
Messages: 93
Offline

Ха не , но сега ја прочитав задачата... Интересно кај МЕНДО што коа ќе речат дека вајда ќе треба да работите со long long се мисли на некој СТРИНГ да напраиш него ли ете така
long long int
Пробај со string некако нешто нека ти текне ако можеш
despotovski01



Joined: 23/02/2014 14:36:12
Messages: 37
Offline

Можеме барокните згради да ги замислиме како правоаголници кои се шират секој месец во сите четири правци, горе, доле, лево и десно. Според тоа, ако барокната зграда на почетокот се наоѓа на позиција (x, y), тогаш за N месеци таа ќе го зафаќа правоаголникот со горна-лева координата (max(1, x - N), max(1, y - N)) и долна-десна координата (min(WIDTH, x + N), min(HEIGHT, y + N)). Притоа, сметаме дека горното-лево поле има координати (0, 0), а координатниот систем има ширина WIDTH и висина HEIGHT.

Проблемот успешно го сведовме на познатиот геометриски проблем на наоѓање на плоштина на поклопувачи правоаголници, кој можеме да го решиме со помош на line-sweep техниката.

Бидејќи кодот е обемен, го ставив на Pastebin, и може да се најде на следниов линк: https://pastebin.com/unpBwXzs

Повеќе за line-sweep можеш да прочиташ тука: https://www.topcoder.com/community/data-science/data-science-tutorials/line-sweep-algorithms/

This message was edited 1 time. Last update was at 02/08/2017 14:23:55

Scratcher



Joined: 21/01/2013 16:53:12
Messages: 14
Offline

Благодарам многу за одговорот @despotovski01

Инаку, еве уште едно решение.

Се користи истата идеја за sweep алгоритамот.

This message was edited 1 time. Last update was at 02/08/2017 18:30:47

 
Forum Index » Задачи од национални натпревари
Go to:   
Powered by JForum 2.1.8 © JForum Team