Задать вопрос
  • Как перебрать из массива до тех пор, пока совпадают даты?

    wataru
    @wataru Куратор тега Алгоритмы
    Lynn «Кофеман», Если элементы не отсортированы, то вы никак не сможете выбрать элементы за определенную дату, не пройдясь по им всем.
  • Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

    wataru
    @wataru Куратор тега Алгоритмы
    Magneto903, А в вашем скрипте ошибка тут:
    var angle = ( vec_1.x * vec_2.x + vec_1.y * vec_2.y )/r*r;
    var num =  1/(Math.cos(angle/2)*Math.sqrt(2+2*Math.cos(angle)))


    В angle у вас храниться значение cos(a), а не угол. А вы потом от этого значения косинуса еще берете косинус.

    Может еще где что-то есть.
  • Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

    wataru
    @wataru Куратор тега Алгоритмы
    Magneto903, Все проще, если у вас полигон задан в порядке обхода против часовой стрелки (можно и по, но надо, чтобы все полигоны так были заданы). Можно понять, в каком порядке задан полигон, если посмотреть на знак векторного произведения двух соседних векторов-сторон. Далее, трюк - можно индексы брать по модулю. Если у вас n точек в полигоне, то они пронумерованы от 0 до n-1 в массиве. И следующая за последней будет ((n-1)+1)%n = 0.

    Дальше, мы хотим подвинуть i-ую веришину. Проще создавать раздутый полигон в новом массиве. Предыдущая имеет номер j=(i+n-1)%n, следующая k=(i+1)%n.

    Далее, вектора нормалей можно взять просто повернув вектора стороны на 90 градусов влево. Если первая сторона имеет вектор (x[i]-x[j], y[i]-y[j]), то нормаль наружу будет (y[i]-y[j], -(x[i]-x[j])). На бумажке проверьте, что это так, например, для вектора (1,0) - нормаль наружу будет идти вниз (0, -1). Точно так же, вторая нормаль будет (y[k]-y[i], -(x[k]-x[i])). Да, эти вектора еще надо обязательно сделать длиной r - на сколько у вас боты обходят полигоны. Поделите на sqrt(vx*vx+vy*vy) и умножте на r все координаты.

    Далее, формулу надо сначала преобразовать через cos(a) и sin(a) - их можно получить, если взять векторное/скалярное произведения нормалей и поделить на длины нормалей):

    1/(cos(a/2)*sqrt(2+2cos(a)) = 1/(1+cos(a)). Внезапно сильно сократилось. И эта формула имеет смысл. Если нормали совпадают, то надо сдвинуться на вектор длины 1. А значит сумму двух нормалей надо будет поделить на 2. И действительно, при a=0, формула даст 1/2. Если нормали перпендикулярны, то они образуют квадрат со сдвинутыми сторонами и их сумма как раз даст диагональ. Надо домножить сумма на 1. Если же нормали прямо в разные стороны смотрят (a=180), то пересечение как-бы в бесконечности (стороны-то параллельны). И действительно, формула даст 1/0.

    Вот вы знаете нормали (длины 1). Взяли их скалярное произведение, получили cosa. И потом к текущей точке прибавьте эти 2 нормали, домноженные на 1/(1+cosa). Не забудьте новую точку считать в новом массиве. Иначе вы для следующей точки будете стороной считать вектор с уже сдвинутой вершины.
  • Почему простой файл на c# детектится как троян?

    wataru
    @wataru
    ShiyanoTetsu, Денег легких захотелось? Имейте ввиду, таких хакеров регулярно сажают. У вас, судя по вопросу, знаний маловато, так что вас точно поймают.
  • Расположите строки массива в порядке возрастания количества одинаковых элементов в каждой строке?

    wataru
    @wataru
    Damian Dante, Ваш код выглядит обрезанным. циклы в С++ идут for(int i=0; i < n; ++i).

    Вот, вы смогли прочесть массив.

    Для подсчета количества одинаковых элементов в каждой строке переберите 2 элемента:
    for (int i=0; i<n; ++i) {
      b[i] = 0; // b - глобальный массив! Объявляйте его вне main()
      for (int j=0; j<m; ++j) {
        for (int p=j+1; p<m; ++p) {
          if (a[i][j]==a[i][p]) ++b[i];
        }
      }
    }


    Теперь сортировка. Используйте std::sort.
    Что бы не перемещать строки, сортируйте их номера. Заведите массив rows с номерами строк, и сортируйте его, используя специальную функцию сравнения, которая сравнивает не сами числа, а строки с этими номерами:

    // в main() после ввода.
     int rows[20];
     for (int i=0; i<n; ++i) rows[i] = i;
     // сортировке передаются первый элемент,
     // элемент после последнего и компаратор -
     // функция сравнения, которая проверяет, что первое
     // значение должно идти раньше второго.
     sort(rows, rows+n, &Cmp);
     // теперь rows отсортирован. Выводим строки rows[0], rows[1]...
     for (int i=0; i < n; ++i) {
       for (int j=0; j<m; ++j) {
         printf("%4d", a[rows[i]][j]);
       }
       printf("\n");
     }
    
    // Отдельная функция, описана перед main():
    bool Cmp(const int &i, const int &j) {
      return b[i] < b[j]; // тут обращаемся к глобальному массиву b.
    }
  • ( sizeof) Почему разные байты у строки, которую создали двумя разными способами?

    wataru
    @wataru
    Whomai, Размер зависит от архитектуры. Может быть 32 бита или 64 бита (4/8 байт). Знаете же, что когда-то процессоры были 32-битные, а сейчас 64-битные? Вот это и есть в том числе длина указателя. Что конкретно у вас будет в программе зависит от операционной системы, процессора и настройки компиляции.
  • Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

    wataru
    @wataru Куратор тега Алгоритмы
    Magneto903, С невыпуклыми все немного сложнее и медленнее (на ваших ограничениях,вроде, должно работать. Можно путь пересчитывать не в каждом кадре, например, а через раз). Никаких оптимизаций (тернарный поиск невозможен, алгоритм дейкстры по всему графу каждый раз, вместо флойда на полигонах без ботов и игрока). Вместо 2 касательных нужно строить все отрезки ко всем вершинам (и удалять те, которые пересекают, в том числе, и текущий многоугольник). Может быть проблема при раздувании в самом начале - многоугольник может сам с собой пересекаться, если у вас возможно что-то вроде спирального лабиринта с узким закрученным проходом. Тут надо будет отрезки полигона добавлять в граф, только если они не пересекаются ни с чем.

    Но можно любой полигон разбить на выпуклые (вместо буквы L - 2 прямоугольника). Это можно делать автоматически (в полигоне найти "вогнутую" вершину, потом взять ее диагональ, которая целиком внутри полигона и не делает два своих конца "вогнутыми". Или составитель карты должен добавлять только выпуклые многоугольники.

    Да, еще забыл написать: даже для выпуклых многоугольников надо их стороны проверять на пересечение с другими многоугольниками и не добавлять в граф - если 2 полигона близко, то после раздутия они могут пересечься. Но это только если у вас боты должны полигоны обходить на небольшом расстоянии.
  • Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

    wataru
    @wataru Куратор тега Алгоритмы
    Magneto903, Вообще, мы убегая точно упремся в стену, если преследователь прямо на нас смотрит, а за нами только стена. Убегающий может действовать только локально. Т.е. вариант 2 - это построить кратчайший путь от преследоваля до убегающего. А потом смотрим, как этот путь идет и продлеваем его. Но тут мы точно упремся в стенку или в другой полигон.

    умнее вариант 3. Тут бот будет прятаться за препятствиями.
  • Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

    wataru
    @wataru Куратор тега Алгоритмы
    Magneto903,

    Нет, если у вас боты приследуют убегающих ботов, то они все в графе (вернее все строят касательные на полигоны). С преследующим ботом просто - он, допустим выбирает ближайшего бота-цель или игрока и идет к ним. Убегающий, наврено, должен убегать от ближайшего? Тут сложно формализовать, что значит убегать. Ясно, когда прямая видемость - бежим строго от. А если нет? Вариант 1 - стоим на месте, вариант 2 - идем в сторону противоположную той, с которой занами едет ближайший преследователь (мы же знаем весь путь). Вариант 3 - бежим к вершине графа, наиболее удаленной от преследователя, а потом двигаемся жадно к соседней вершине графа, которая наиболее удалена от преследователя. Все варианты могут выдавать какое-то странное поведение.
  • Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

    wataru
    @wataru Куратор тега Алгоритмы
    Magneto903, Если вы хотите убегающих ботов, то это немного другая задача. Можно использовать уже найденные расстояния от игрока до всех точек в графе и, например, стремится все время идти к той точке, которая от игрока наиболее удалена локально. Тогда бот будет идти от игрока и пытаться прятаться за препятствием. Ну и отдельно, если игрок в прямой видимости - идти прямо от него.

    Зачем что-то между ботами делать, мне не понятно, но ботов мало, вы можете и лучи между ними в граф добавить, все будет быстро.
  • Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

    wataru
    @wataru Куратор тега Алгоритмы
    twobomb, Про A* вы первый раз написали. И это не жадный алгоритм и называть его жадным некорректно, хоть жадность там и использутеся в качестве эвристики. Далее, в данной задаче, даже если работать на сетке, BFS может оказаться сильно быстрее, если гнать его один раз от игрока и найти пути для всех ботов сразу же. A* так сделать не получится.
  • Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

    wataru
    @wataru Куратор тега Алгоритмы
    Magneto903, 100 полигонов, 10 ботов 60 раз в секунду будет работать даже без всех оптимизаций, если полигоны не большие (<10 вершин) Флойда наверно, надо, таки, вместо дейкстры использовать.

    Если полигоны могут быть по 1000 вершин, то надо тернарный поиск ворочать. BSP будет работать моментально хоть для 1000 полигонов по 1000 вершин и 100 ботов.
  • Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

    wataru
    @wataru Куратор тега Алгоритмы
    twobomb
    > Ну это затратная операция раздувания каждого, хотя можно сделать ее один раз в начале и хранить для каждого параметры раздутого и сдутого, ору... ну там опять вылезут всякие приколы когда полигон в полигон залазит, и понятно как это считать крч...

    Ощущение, что вы вообще не в теме. С одной стороны несете лютый бред и предлагаете делать жадный алгоритм посика пути (Хоть немного теорию подучите, блин. Теория графов в любом курсе computer science дается в самом начале. Это самая заезженная и базовая тема!) С другой сторны, вы эту простейшую операцию, которая один раз проходит по всем вершинам полигонов, называете затратной. Блин, это прямо во время чтения координат можно делать!

    Когда полигон залезет на полигон - значит там прохода не было. Бот не помещается в эту щель. Все ребра в графе через эту часть будут удалены, потому что они пересекаются с полигонами. Для алгоритма эти 2 полигона сольются в один.
  • Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

    wataru
    @wataru Куратор тега Алгоритмы
    twobomb, У вашего алгоритма проблема в том, что проход мужду полигонами может быть не выравнен по сетке. Т.е. и текущий квадрат и чуть левее пересекают полигоны. А посерединке пройти можно. Но и без этого - он слишком медленный. Видно, что вы не в курсе алгоритмов. Предлягать для поиска кратчайшего пути жадный алгоритм - это дичь. Есть куча стандартных алгоритмов поиска пути на графе Хоть тот же BFS. Но для работы на сетке есть еще более быстрый алгоритм - jump point search. Только в этой задаче с произвольными полигонами он не подходит.
  • Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

    wataru
    @wataru Куратор тега Алгоритмы
    twobomb, Не этот. Бот маленький (если он помещается между треугольниками. Значит труегольники становятся чуть чуть больше, на расстояние примерно равное половине расстояния между ними. В итоге они начинают просто касаться. Далее алгоритм найдет касательную к верхней вершине левого треугольника. Из нее - касательную к нижней вершине правого треугольника, из нее - к синему квадрату.

    Но лучше, чтобы проблем с точностью не было, не делать так, что боты впритык к полигонам ходят. Лучше оставить между треугольниками чуть больше расстояния. Тогда после раздувания они будут очень близко, но не будут касаться.
  • Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

    wataru
    @wataru Куратор тега Алгоритмы
    Magneto903, Надо еще для каждого ребра графа тут проверять, что оно не пересекается с ни с одним полигоном. Еще, как я распиал в своем ответе, достаточно рассматривать только касательные между точками к полигону (ну и стороны полигонов). Это сильно снижает количество ребер и ускоряет поиск на графе.
  • Как находить производную y' при x=0 и y=0.неявная функция?

    wataru
    @wataru Куратор тега Математика
    Michelin123, Ваша функция в (0,0) не диффиренцируема: https://www.wolframalpha.com/input/?i=plot+%28x%5E...

    Там пересекаются 3 линии. Производной в этой точке нет.
  • Как найти фигуру основания сетки?

    wataru
    @wataru
    mIka01, Все-равно непонятно. Какая фигура в основе сетки на картинке?

    Можете как-то формализовать задачу? Вот есть набор точек с координатами. Фигура (полигон? Набор точек?) образует сетку, если... что? Например, набор точек состоит из нескольких сдвинутых копий фигуры относительно одной прямой с равным сдвигом. Или все заданные точки покрываются копиями фигуры, сдвинутыми вдоль прямоугольной сетки.
  • Как правильно написать условие проверки для функции?

    wataru
    @wataru Куратор тега Математика
    Dragon1, Там надо проверить 1) нет корня из отицательного числа в числителе, 2) нет корня из отрицательного числа в знаменателе, 3) знаменатель не 0.
  • Как правильно написать условие проверки для функции?

    wataru
    @wataru Куратор тега Математика
    Dragon1, Это же условие для вывода "not defined" (судя по последнему, которое проверяет, что знаменатель == 0). И оно not defined, если корень из отрицательного числа, или x+1<0 или x < -1.