Мои уточнения:

•  Пусть верхняя левая точка льдины попадает на течениеА, и какая-то другая ее точка тоже попадает на какое-то течение (другое или то же самое - неважно). Куда поплывет льдина? Смотрим только на левую верхнюю точку (остальная часть льдины движется в том же направлении).
•  Пусть в одной точке есть сразу два течения: течениеА (...-а1-с1-е1-...) и течениеВ (...-а2-с1-е2-...). Мы находимся в точке с1. Куда мы поплывем? Мы рассмотрим по отдельности всевозможные пути движения из с1: сначала поплывем по течениюА в е1 и рассмотрим этот вариант до конца; потом вернемся в с1 и поплывем в е2, рассмотрим этот вариант до конца.
  Короче не надо складывать течения, находить среднее арифметическое между ними, думать, вклад какого течения должен быть больше и т.п..
•  Льдина уперлась в берег. Если ее повернуть, то она сможет плыть дальше. Льдина может поворачиваться? Нет.
•  Что значит "как далеко"? Путь (не перемещение!) максимальной длины.

Пока я думаю, что остров, льдина и течение - по сути одно и то же. Они будут объектами одного класса "многоугольник" (я знаю, что ломаная - не полигон... но сейчас можно так думать).

Многоугольник:
- число вершин n;
- двумерный динамический массив размерности (n-1) с координатами;
- квадрат(ы), в к-м (к-х) находится многоугольник (льдина или остров) в данный момент (а не поделить ли условно карту на разделы А, B, C, D, ...? тогда если у меня льдина будет в квадратеА, а какой-то остров в В и С, то я сразу буду знать, что они не пересекаются); видимо, это тоже будет структура из числа текущих квадратов и массива этих квадратов.

Все течения-объекты можно хранить в структуреТечения (кол-во течений; одномерный массив из течений-объектов). То же самое с островами.

Еще будут
список (двунаправленный), хранящий индексы точек ломаных, формирующих текущее перемещение (1-ый индекс - номер течения, 2-ой индекс - номер точки в этом течении)
максимальный путь, к-й мы смогли проплыть за всю  историю программы
путь текущего перемещения

Собственно, все получается не так уж и сложно (рекурсия):

узнаем текущую точку левой верхней вершины льдины к0 (узнаем ее из последнего элемента списка перемещений);
бежим по течениям, ищем к0;
    если не нашли к0, то
        считаем пройденный путь по списку перемещений, сравниваем его с максимальным
        из последнего элемента списка берем индекс течения, запоминаем его в переменную stop
         удаляем последний элемент списка, точкой к0 становится последний элемент списка
        бежим по течениям дальше (ищем к0, причем начинаем бежать с течения stop+1 - предыдущие течения мы уже рассматривали)
    нашли к0 в i-том течении;
        заглянули в следующую координату i-ого течения и вычислили, на сколько мы должны сместиться;
        поместили координаты предполагаемой смещенной льдины в многоугольник лТест;
        проверили, а не пересекается ли лТест и какой-нибудь остров;
            увидели пересечение
                 продолжили бежать по течениям (начали с течения i+1, ищем к0)
            нет пересечения
                в  спискеПеремещений выделили память для нового элемента;
                записали в новый элемент индекс текущего течения (i) и индекс найденной в нем точки;
                точкой к0 становится последний элемент списка (т.е. через индексы его вычисляем, разумеется);
                ищем к0 в течениях (начинаем с первого);

Добавлено через 1 минуту и 5 секунд
Вот только если течения где-то будут образовывать цикл (будут замыкаться), то моя программа никогда не закончит работать...

Тихо сам с собою я веду беседу...

Мне тут подсказали одно словосочетание: сумма Минковского. Правильно  ?

Не знаю, что это, и какое отношение это может иметь к задаче 


Ну в таком случае и ответ на задачу будет "бесконечность" - а это вообще допускается условием?

Я так просмотрел алгоритм, что-то в нём не видно обработки такого случая: есть какой-нибудь остров, и мимо него проходит (совсем близко) течение, то такое, что на концах его как раз всё отлично, льдина с островом не пересекается, но пока она будет плыть от одного конца до другого, она обязательно пересечёт остров, т.е. на самом деле проверок только на концах отрезка недостаточно. Кроме них, надо проверить, что никакая вершина полигонов-островов не попадёт в ту полосу (траекторию), которую образует льдина. Это на самом деле очень хитрый момент, и здесь надо хорошо подумать, как это дело обнаруживать. В твоём случае можно попробовать и численно проверять (численный метод гарантий не даст, но на не слишком больших и хитрых тестах будет всегда работать), например так - разбить текущий отрезок течения штук на 100, и просто проверить в каждой, что льдина не пересеклась. Развитие этого метода - в каждом из 100 отрезков запустить тернарный поиск (это будет уже совсем сложно завалить  ).

После того, как мы научимся для каждого отрезка течения проверять, можем мы по нему проплыть или нет, у нас получится такая задача: дан ориентированный взвешенный граф, найти в нём путь наибольшей длины. Если в нём есть цикл, достижимый из стартовой вершины, то ответ бесконечность. Иначе - ответ можно найти тривиальной динамикой (пусть d[v] - путь максимальной длины, начинающийся в v; тогда d[v] = максимум (edge_len + d[edge_to]) по всем рёбрам (v,edge_to) длины edge_len. Поэтому после построения графа задача решится за O(N)

Ок, мы возьмем одно течение, будем пробовать перемещать по нему льдину (причем если мы в какой-то части течения не не смогли проплыть, то мы все равно продолжаем проверять дальше - мы можем попасть в продолжение этого течения с какого-то другого течения...). Потом удаляем это течение и загружаем следующее...

Большой вопрос - как при этом строить граф (и из чего вообще его строить?).
Самый вероломный и тупой способ - каждую точку плоскости принять за вершину. Несложно догадаться, что на плоскости размера 10х10 мы получим 100 вершин, на 30х30 - 900... Еще немного расширимся: 40х40 - и уже 1600 вершин  . Комп может зависнуть весьма на долго (а для нормальных маневров нужно хотя бы 100х100 - 10000 вершин     ).
Поэтому понятно, что как вершины нужно рассматривать только те точки плоскости, в которые мы можемт приплыть (или уплыть). Здесь возникает несколько проблем:

• ну ок, мы взяли как вершину точку (4,5), потому что она где-то участвовала; потом в каком-то течении1 мы опять натыкаемся на (4,5) и мы должны уже как-то присовокупить новую информацию из течения1 к уже созданной (4,5) - т.е. при каждом успешном передвижении мы должны узнавать, встречались мы уже с этой точкой или нет (неужели каждый раз будет запускаться цикл с поиском???)
• если пытаться хранить граф в виде какой-нибудь матрицы или массива чего-нибудь (самые удобные представления для анализа), то мы не знаем, сколько вершин нам понадобиться создать; получается, мы будем сначала создавать список списков смежности, а потом переводить его в матрицу (смежности, например)? а ведь при построении списка списков придется еще узнавать, сталкивались ли мы раньше с этими вершинами ли нет.
  Какая-то каша получается... Ничего не понимаю.

Я думала об этом и решила упростить себе задачу: при описании течений-ломаных следующая точка обязана прилегать к текущей (т.е. после (x,y) в течении может быть только что-то из этого: (x-1,y-1), (x-1,y), (x-1,y+1), (x,y+1), (x+1,y+1), (x+1,y), (x+1,y-1), (x,y-1) ; разные (x-3,y+5) не допускаются...).


Мне сейчас совсем не до этого :( : у меня еще куча других предметов и занятий, впереди одна из самых тяжелых сессий...

...

Это сообщение отредактировал(а) KasMP - 16.5.2009, 18:55

Граф строить из всех точек, принадлежащих всем течениям. От размера поля само по себе количество вершин в графе зависеть не будет. Между вершинами a и b проводить ребро, когда отрезок, соединяющий эти две точки, есть хотя бы в одном течении.

Я же правильно понял, что течение - это просто как бы набор стрелок? Стрелка из одной точки в её соседа. И мы можем все эти стрелки от всех отрезков собрать в одну кучу, и получится такой граф. Из этого графа надо удалить все "плохие" переходы - т.е. в которых льдина будет пересекать какой-нибудь остров. И в этом графе собственно мы и должны найти длиннейший путь, начинающийся в заданной стартовой вершине.


Ну ладно, тогда можно забить на внутренние точки отрезков (хотя на самом деле всё равно их надо рассматривать, но, думаю, в качестве решения по Практике по ЭВМ пойдёт  ).

В итоге, чтобы построить граф, нам надо проверить, пересекаются ли два полигона.

Ну можно и так сказать  .
Течение - это набор точек. Например: (0,0), (0,1), (1,2), (2,3), (2,4), ... .





Это все понятно, проблема уже на следующем шаге:

Ну это трудности совсем уж технические.
Делаем граф:

Делаем структуру данных, которая будет по номеру точки возвращать саму точку и наоборот:

Ну и делаем функцию, которая по координатам точки возвращает её номер как вершины (либо уже имеющийся, либо создаёт новую вершину):

После этого добавление любого ребра и прочие операции становятся совсем прозрачными, например:


Это сообщение отредактировал(а) maxdiver - 4.5.2009, 23:02

maxdiver , я понимаю, как это реализовать  . Опишу я и private-переменные, и функции доступа к ним сделаю, и функцию, бегающую по данным в ОП, тоже... Вопрос скорее в том, насколько это рационально.

Ну а в чём тогда вопрос? При каждом передвижении мы за logN в мэпе находим, встречались мы с этой точкой или нет, и если встречались, то найдём её старый номер. Никакого цикла по старым точкам не будет.
Асимптотика всей программы, кроме той части, где проверяется пересечение льдины и островов, будет N logN, где N - количество точек во всех течениях. Даже для ста тысяч это будет работать быстро. Другое дело, что пересечение льдины и островов будет самой тяжёлой операцией (оно тоже будет N раз вызываться).

  
Новое слово  .

Под циклом я имела в виду цикл с поиском вершины с нужным названием среди уже существующих (т.е. тех, которые уже где-то участвуют и образуют какое-то ребро). Что-то не так ?
        
Кстати, какой алгоритм ты бы порекомендовал использовать для этого? Их так много, прямо глаза разбегаются...
Мне нужно 2 алгоритма пересечения: один с результатом типа bool (т.е. достаточно просто знать, пересеклось или нет), другой - с результатом-полигоном (т.е. нужно полностью построить то, что получится при пересечении).

Ну так не будет такого цикла. Будет просто вызов: ids[p], мэп (map  ) вернёт номер вершины с заданными координатами, причём потратит на это порядка логарифма операций. В этом вся прелесть мэпа 


Если за большое число операций (размер одного полигона умножить на размер другого), то я бы написал так: переберём отрезки одного полигона и каждый проверим, что он лежит внутри другого (если он лежит частично, то и оставим от этого отрезка нужный кусок). В результате у нас получится куча отрезков, в которой надо найти внешнюю грань...
Вообще говоря, эту задачу можно решить за намного меньшее число операций (порядка суммы размеров полигонов), и вполне возможно, что и кода будет меньше, но я пока не совсем представляю, как это пишется.

Вобщем задачка решается так:

1. Вычислить льдину вектор:
вычислить все векторы, начинающиеся в левой верхней вершине и заканчивающиеся в других вершинах;
потом все векторы отобразить (x=-x, y=-y).

2. Расширить каждый остров на один из векторов льдины-вектора:
взять вектор i из льдины-вектора;
найти расстояние между
- прямой, задаваемой точками p (с номером j) и p (с номером j+1) (p - точки острова, который мы сейчас расширяем);
и
- точкой, получаемой при отложении вектора i (который из льдины-вектора) от этой прямой;
запомнить вектор (из льдины-вектора), дающий максимальное расстояние;
в расширяемом острове сдвинуть точки p (с номером j) и p (с номером j+1) на вектор i.

3. Взять левую верхнюю вершину (ЛВВ) льдины, двигать ее по течениям, строить орграф.
(вообще не очень понятно, как это делать... ясно лишь то, что нужно уметь определять, находиться точка внутри выпуклого многоугольника (ВМ), на его границе или вообще вне него)

4. В орграфе найти максимальный путь.
(отсюда понятно, что в п.3 мы должны строить такое представление графа, по которому удобно искать максимальный путь)


Требуются алгоритмы:
а) поиска расстояния между стороной ВМ и точкой (при этом точка не должна попадать внутрь ВМ);
б) определения, где лежит точка относительно ВМ: [на границе]/[вне его] или внутри;
в) поиск максимального пути в орграфе.

Добавлено через 35 секунд

Это что-то из STL? Или что ?

Еще при построении орграфа мы не учли один важный момент...
Вершинами графа будут не только те точки ломаных, между которыми льдина может перемещаться: если два отрезка двух ломаных пересекаются, то точка их пересечения - новая самостоятельная вершина.