sirenko, я лишь сказал, как найти площадь пустого пространства среди заданных блоков. Как их упаковывать- это отдельная очень сложная задача. Можно предположить, что у вас не будет островов если все коробки класть так, чтобы они положенного уже как-то касались. Тогда не надо мучатся с лучами. Надо только учесть, что одна "пустая" область максимального размера будет на самом деле бесконечной внешностью: ее надо проигнорировать.
Еще, стоит полумать, вдруг в задаче можно класть блоки так, чтобы замкнутых пустот не образовывалось вообще.
sirenko, увы, при попытке описать метод нашелся косяк. Обход в ширину со сжатием координат быстрее. Это будет O(n^2).
Другой быстрый метод, действительно за n log n: построить граф из линий и обойти все ребра. Что-то вроде этого: e-maxx.ru/algo/facets
Надо построить граф, где вершины - это углы блоков, а ребра - линии между ними. Для этого точки надо отсортировать 2 раза: по x, y а потом по y, x.
Но проблема этого алгоритма, что он не обработает области с дырками, вроде пустоты в которой коробками ограниченна другая область. Это можно обойти, если добавить еще линии на граф. Из каждого левого верхнего угла пустите вверх луч, пока он не пересечет другой блок. Это можно все за n log n сделать методом сканирующей прямой снизу вверх. У вас может начаться луч или встретится нижняя грань блока. Храните лучи в балансированном дереве (set) и при границе отсекайте те лучи, которые с ней пересекаются. В c++ это легко делается через lower_bound у set, в js вам придется писать свое BST похоже.
Лучи, которые не пересеклись ни с чем, надо запомнить.
Потом, когда вы все области получили, если в ней есть ребро от блока по часовой стрелке и нет верхнего ребра блока с незакрытым лучем - это пустая область.
Еще есть метод сканирующей прямой и системы непересекающихся множеств. Работать это все будет где-то за O(n log n), но без хорошего опыта с алгоритмами вы это вряд ли напишите. Но если хотите, могу объяснить.
хм, а если в таком случае для i-го веса перебирать все N предметов ?
Не поможет. Проблема в том, что вы не знаете, какие из предметов можно брать для текущего i-ого веса - вдруг они вам очень нужны в конце будут. И просто по одной последней строке вы никак это не определите вообще. И в итоге ваше восстановление ответа может взять один предмет несколько раз, или, если этого избегать, прийти в тупик: все возможные предметы для i-ого веса уже взяты в ответ и что делать вообще непонятно.
Иногда можно прям в массиве хранить множество всех предметов, Но это уже не O(S) памяти. Возможно, это все равно меньше O(SN) для полной матрицы, но не факт.
thirteen_bit, Ну просто перебрать все точки и найти ту, которая дает максимум. Если ищите среди выпуклого множества, то можно бинарным поиском искать - так быстрее, но сложнее.
floppa322, Зависит от задачи. Если у вас можно предметы использовать только по одному разу, то нельзя из только последней строки восстановить ответ. В некоторых задачах, как рюкзак без цен с повторениями, действительно, трюк с сокращением таблицы ДП не имеет недостатков.
FlashDok, Ну вот подумайте: если прямоугольник очень высокий, весь луч ни разу не отражается. его длина не зависит от высоты вообще. Если прямоугольник где-то в 2 раза ниже, чем если бы луч был от угла в угол, то луч был бы из двух сегментов. Если их выпрямить - то это будет все тот же прямой луч все той же длины. Т.е. очевино мы можем высоту менять очень в широких пределах не меняя длину.
Если все еще не верите, то в автокаде поиграйтесь с прямоугольником не меняя его длину и угол наклона.
FlashDok, а высота и не учитывается. Если вам надо именно до правой стенки длину подсчитать, то она от высоты не зависит. В более низких прямоугольниках будет просто больше отражений, но длина луча такая же.
FlashDok, где вы ее нашли и что она должна искать? Не подходит. Только первое слагаемое оставьте. Замените еостнус на синус, и если все еще не подходит.
kan3k1k3n, У вас там уже одно целое число. Если же вы хотите, чтобы в файле было "7", то читайте и пишите в текстовом режиме. Открывайте файл с "t" вместо "b" и читайте/пишите fscanf/fprintf, а не fread/fwrite.
Skodio29, да, придется только так. Любая библиотека, что вы откопаете, будет именно так и делать. И это достаточно простой код, чтобы написать его руками.
Xiran, Не влиет, конечно, но если вам нужна переносимость, то используйте, например int32_t. Так-то размер ptrdiff гарантируется быть хотя бы 17 бит, а сколько их там на другой платформе - вы знать не можете.
Скорее всего у вас там где-то Undefinded behavior. Ошибка, короче. Выложите код, чтобы его было удобно читать. Например, кажый файл в отдельный спойлер и в теге code. Или на pastebin. Качать архивы и в них ковырятся ради вас никто не будет.
Еще, стоит полумать, вдруг в задаче можно класть блоки так, чтобы замкнутых пустот не образовывалось вообще.