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. Качать архивы и в них ковырятся ради вас никто не будет.
Adamos, Ох, да. У вас решение за O(n^2) вместо O(n). Это называется "волновой алгоритм". Тоже из теории графов. Для уже упомянутого выше случая
в других вариантах было намного больше этажей
- ваше решение никуда не годится.
Вообще, математическая модель тут - граф. Вы можете сколько угодно отворачиваться от этого факта, но любое ваше решение в итоге будет алгоритмом на графе. Просто если теорию знать, то сразу понятно, какое решение тут хорошее, а какое - не очень. Это как, если вам дано квадратное уравнение, даже если там не x, а количество зайцев и все словами описано, то вы как его не решайте, в итоге все равно получите числа из формулы с дискриминантом.
Другой быстрый метод, действительно за n log n: построить граф из линий и обойти все ребра. Что-то вроде этого: e-maxx.ru/algo/facets
Надо построить граф, где вершины - это углы блоков, а ребра - линии между ними. Для этого точки надо отсортировать 2 раза: по x, y а потом по y, x.
Но проблема этого алгоритма, что он не обработает области с дырками, вроде пустоты в которой коробками ограниченна другая область. Это можно обойти, если добавить еще линии на граф. Из каждого левого верхнего угла пустите вверх луч, пока он не пересечет другой блок. Это можно все за n log n сделать методом сканирующей прямой снизу вверх. У вас может начаться луч или встретится нижняя грань блока. Храните лучи в балансированном дереве (set) и при границе отсекайте те лучи, которые с ней пересекаются. В c++ это легко делается через lower_bound у set, в js вам придется писать свое BST похоже.
Лучи, которые не пересеклись ни с чем, надо запомнить.
Потом, когда вы все области получили, если в ней есть ребро от блока по часовой стрелке и нет верхнего ребра блока с незакрытым лучем - это пустая область.
Площадь многоугольника считайте так: https://e-maxx.ru/algo/polygon_area
Это очень сложно релизовать.