И еще, история про водку…
ВоД пили мы сколько помню себя "Хортицу, зять даже причу придумал, водка может быть любой ес ли она “Хортица”, вижу просто “Архангельскую” , когда хортица пропала, чела напрягли, была хорта, а теперь и ее нет. Перебрал много, остановился на “Белая Березка”, гыы наш СНТ в котором теперь живу практически круглогодично, называется “Березка”, так вооот Архангельская не зашла…
Все, устал писать… 
Ну… Наверно, всё надоедает. Да, была Хортица у нас в своё время популярная, потом мы от водки как то отошли - всё коньяк… А сейчас вот родственник Архангельскую посоветовал. Но там они разные бывают, на травах всяких - это тоже не по мне. В общем, всё на любителя.
Берёзку постараюсь попробовать, при случае.)
1 лайк
Главное - чтоб не Северодвинскую. А то хвост вырастет еще.
Боже, они туда ягель суют. Зачем…
Не, ну а чо такова?
Тут главное условие понять, а дальше - уже просто.
Интересно, никто еще не доказал теорему, что при наличии О(n^2) обязательно должно быть и О(n*log(n))?
Лично я все равно склоняюсь в пользу “растрового” решения. Как известно, если в первом акте на стене ружье … в смысле, если упомянуто n*m, то в последнем - нужно решать дискретную задачу. А она никак не может быть больше О(n*m).
Хотя, все равно два алгоритма: Брезенхем и волна.
??? 
хорошо, когда в голове такой инструментарий, а что нам, сирым, делать?
Так выпьем же за образование! До дна!
такое можно искать, если есть явный способ “уполовинить” задачу.
учиццо, учиццо, и ысчорас учиццо! (с) Комми знают, кто это сказал. 
ЗЫ: Блин! Вот реально щас грех жаловаццо! Я в конце 80-х на МехМате искал хорошие книги по математике по букинистам. На Калининском, на Ленинском, на Столешникове…
А сейчас все в Инете есть. Даже в Вики просто прочесть можно почти любую концепцию и там же список литературы со ссылками. И у них “знаний в головах нет”?! Пипец - лентяи!
1 лайк
как бы книг сейчас есть, но системности без препода достичь трудно:(
ну, за полиграфию!
мне думается решением задачи будет не “нахождение всех пересечений а затем пути по этим пересечением” ,а минимального но достаточночо условя проверив которе можно будет сказать “может ли муравей пересечь или нет” …чисто как пример такого условия:
если отобразить все отрезки на абсциссу , и если сумма таких не перехлестывающихся отображений < ширины которую надо пересечь, то муравей точно не сможет пересечь.
ну и надо будет доказать, что минимальное условие - достаточно.
Точно! Для ускорения решения можно сначала посмотреть проекции отрезков на оси. Уже предварительно поймём, начинается ли какой-либо отрезок с x=0 и пересекается ли его конец с началом других отрезков. Аналогично по Y.
И?
Конечно, если не достигают, то дальше можно не искать, но это (посмотреть на проекции) сама по себе операция не бесплатная и делать это ради редкого частного случая? не вижу смысла.
если у нас есть координаты начала и конца отрезков , то проэкция на ось х отрезка t([x1_0,y1_0] , [x1_1,y1_1]) → (х1_0,х1_1) ,нет ? для всех осей и отрезков 2n операций ,что меньше n^2
Хорошо.
- Начиная слева находим ближайшую пару с пересекающимися проекциями по X
- Если пара найдена, сравниваем проекции по Y.
- Если и Y пересеклось, значит отрезки пересек…
Не, я лох. На обеде порисую, подумаю)
помню тут меня гнобили за реальную задачу - расчёт объёма жидкости в бочке лежащей на боку по измерению линейкой (стандартная ежесменная процедура,задавал на собеседовании)
Тогда поворачиваем координаты так, чтобы интересующий отрезок давал нулевую длину(точку) и “смотрим” вдоль неё. А почему нет?
(заметим, что прямая, на которой лежит отрезок делит плоскость на две полуплоскости. Для краткости будем называть прямую, на которой лежит отрезок - “прямой этого отрезка”).
Общее правило здесь такое:
отрезки имеют хотя бы одну точку пересечения, если для каждого из двух отрезков верно утверждение: либо концы отрезка лежат в разных полуплоскостях, образованных прямой другого отрезка , либо хотя бы один из концов лежит на прямой другого отрезка.
Не забываем - это должно быть верно для обоих отрезков.
Проверяется это любым способом. Можно в лоб (выписываем уравнение прямой по двум точкам и сравниваем), можно по знаку векторного произведения - как угодно.
не хватает точных условий задачи