Author |
Message |
30/07/2017 18:27:02
|
Scratcher
Joined: 21/01/2013 16:53:12
Messages: 14
Offline
|
http://mendo.mk/Task.do?id=466
Дали има некој идеја за решение на задачата?
Досега стигнав до ова решение кое поминува само на првите 6 тест случаеви
а на останатите вади runtime error(претпоставувам заради матрицата city)
|
|
|
01/08/2017 16:43:59
|
Perez
Joined: 18/10/2014 18:53:59
Messages: 93
Offline
|
Користи Debugger, ќе ти помогне да го најдеш Runtime Errorot
|
|
|
01/08/2017 17:14:09
|
Scratcher
Joined: 21/01/2013 16:53:12
Messages: 14
Offline
|
@Perez
Благодарам за одговорот.
Инаку, проверив дека причината за runtime error-от е тоа што неможе да се иницијализира матрица [750000][750000]
Значи, останува да се најди сосема друго решение.
Ти ја имаш решено?
|
|
|
01/08/2017 21:11:21
|
Perez
Joined: 18/10/2014 18:53:59
Messages: 93
Offline
|
Ха не , но сега ја прочитав задачата... Интересно кај МЕНДО што коа ќе речат дека вајда ќе треба да работите со long long се мисли на некој СТРИНГ да напраиш него ли ете така
long long int
Пробај со string некако нешто нека ти текне ако можеш
|
|
|
02/08/2017 14:22:58
|
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
|
|
|
02/08/2017 18:22:07
|
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
|
|
|
|
|
|