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.
}
Whomai, Размер зависит от архитектуры. Может быть 32 бита или 64 бита (4/8 байт). Знаете же, что когда-то процессоры были 32-битные, а сейчас 64-битные? Вот это и есть в том числе длина указателя. Что конкретно у вас будет в программе зависит от операционной системы, процессора и настройки компиляции.
Magneto903, С невыпуклыми все немного сложнее и медленнее (на ваших ограничениях,вроде, должно работать. Можно путь пересчитывать не в каждом кадре, например, а через раз). Никаких оптимизаций (тернарный поиск невозможен, алгоритм дейкстры по всему графу каждый раз, вместо флойда на полигонах без ботов и игрока). Вместо 2 касательных нужно строить все отрезки ко всем вершинам (и удалять те, которые пересекают, в том числе, и текущий многоугольник). Может быть проблема при раздувании в самом начале - многоугольник может сам с собой пересекаться, если у вас возможно что-то вроде спирального лабиринта с узким закрученным проходом. Тут надо будет отрезки полигона добавлять в граф, только если они не пересекаются ни с чем.
Но можно любой полигон разбить на выпуклые (вместо буквы L - 2 прямоугольника). Это можно делать автоматически (в полигоне найти "вогнутую" вершину, потом взять ее диагональ, которая целиком внутри полигона и не делает два своих конца "вогнутыми". Или составитель карты должен добавлять только выпуклые многоугольники.
Да, еще забыл написать: даже для выпуклых многоугольников надо их стороны проверять на пересечение с другими многоугольниками и не добавлять в граф - если 2 полигона близко, то после раздутия они могут пересечься. Но это только если у вас боты должны полигоны обходить на небольшом расстоянии.
Magneto903, Вообще, мы убегая точно упремся в стену, если преследователь прямо на нас смотрит, а за нами только стена. Убегающий может действовать только локально. Т.е. вариант 2 - это построить кратчайший путь от преследоваля до убегающего. А потом смотрим, как этот путь идет и продлеваем его. Но тут мы точно упремся в стенку или в другой полигон.
умнее вариант 3. Тут бот будет прятаться за препятствиями.
Нет, если у вас боты приследуют убегающих ботов, то они все в графе (вернее все строят касательные на полигоны). С преследующим ботом просто - он, допустим выбирает ближайшего бота-цель или игрока и идет к ним. Убегающий, наврено, должен убегать от ближайшего? Тут сложно формализовать, что значит убегать. Ясно, когда прямая видемость - бежим строго от. А если нет? Вариант 1 - стоим на месте, вариант 2 - идем в сторону противоположную той, с которой занами едет ближайший преследователь (мы же знаем весь путь). Вариант 3 - бежим к вершине графа, наиболее удаленной от преследователя, а потом двигаемся жадно к соседней вершине графа, которая наиболее удалена от преследователя. Все варианты могут выдавать какое-то странное поведение.
Magneto903, Если вы хотите убегающих ботов, то это немного другая задача. Можно использовать уже найденные расстояния от игрока до всех точек в графе и, например, стремится все время идти к той точке, которая от игрока наиболее удалена локально. Тогда бот будет идти от игрока и пытаться прятаться за препятствием. Ну и отдельно, если игрок в прямой видимости - идти прямо от него.
Зачем что-то между ботами делать, мне не понятно, но ботов мало, вы можете и лучи между ними в граф добавить, все будет быстро.
twobomb, Про A* вы первый раз написали. И это не жадный алгоритм и называть его жадным некорректно, хоть жадность там и использутеся в качестве эвристики. Далее, в данной задаче, даже если работать на сетке, BFS может оказаться сильно быстрее, если гнать его один раз от игрока и найти пути для всех ботов сразу же. A* так сделать не получится.
Magneto903, 100 полигонов, 10 ботов 60 раз в секунду будет работать даже без всех оптимизаций, если полигоны не большие (<10 вершин) Флойда наверно, надо, таки, вместо дейкстры использовать.
Если полигоны могут быть по 1000 вершин, то надо тернарный поиск ворочать. BSP будет работать моментально хоть для 1000 полигонов по 1000 вершин и 100 ботов.
twobomb
> Ну это затратная операция раздувания каждого, хотя можно сделать ее один раз в начале и хранить для каждого параметры раздутого и сдутого, ору... ну там опять вылезут всякие приколы когда полигон в полигон залазит, и понятно как это считать крч...
Ощущение, что вы вообще не в теме. С одной стороны несете лютый бред и предлагаете делать жадный алгоритм посика пути (Хоть немного теорию подучите, блин. Теория графов в любом курсе computer science дается в самом начале. Это самая заезженная и базовая тема!) С другой сторны, вы эту простейшую операцию, которая один раз проходит по всем вершинам полигонов, называете затратной. Блин, это прямо во время чтения координат можно делать!
Когда полигон залезет на полигон - значит там прохода не было. Бот не помещается в эту щель. Все ребра в графе через эту часть будут удалены, потому что они пересекаются с полигонами. Для алгоритма эти 2 полигона сольются в один.
twobomb, У вашего алгоритма проблема в том, что проход мужду полигонами может быть не выравнен по сетке. Т.е. и текущий квадрат и чуть левее пересекают полигоны. А посерединке пройти можно. Но и без этого - он слишком медленный. Видно, что вы не в курсе алгоритмов. Предлягать для поиска кратчайшего пути жадный алгоритм - это дичь. Есть куча стандартных алгоритмов поиска пути на графе Хоть тот же BFS. Но для работы на сетке есть еще более быстрый алгоритм - jump point search. Только в этой задаче с произвольными полигонами он не подходит.
twobomb, Не этот. Бот маленький (если он помещается между треугольниками. Значит труегольники становятся чуть чуть больше, на расстояние примерно равное половине расстояния между ними. В итоге они начинают просто касаться. Далее алгоритм найдет касательную к верхней вершине левого треугольника. Из нее - касательную к нижней вершине правого треугольника, из нее - к синему квадрату.
Но лучше, чтобы проблем с точностью не было, не делать так, что боты впритык к полигонам ходят. Лучше оставить между треугольниками чуть больше расстояния. Тогда после раздувания они будут очень близко, но не будут касаться.
Magneto903, Надо еще для каждого ребра графа тут проверять, что оно не пересекается с ни с одним полигоном. Еще, как я распиал в своем ответе, достаточно рассматривать только касательные между точками к полигону (ну и стороны полигонов). Это сильно снижает количество ребер и ускоряет поиск на графе.
mIka01, Все-равно непонятно. Какая фигура в основе сетки на картинке?
Можете как-то формализовать задачу? Вот есть набор точек с координатами. Фигура (полигон? Набор точек?) образует сетку, если... что? Например, набор точек состоит из нескольких сдвинутых копий фигуры относительно одной прямой с равным сдвигом. Или все заданные точки покрываются копиями фигуры, сдвинутыми вдоль прямоугольной сетки.
Dragon1, Это же условие для вывода "not defined" (судя по последнему, которое проверяет, что знаменатель == 0). И оно not defined, если корень из отрицательного числа, или x+1<0 или x < -1.
Dragon1, Да, потому что cos(x) == 1 только для чисел вида pi/2, 3pi/2,...
Вы эти числа в программе никогда не получите, если только прямо с них не начинаете.
Вот, вы смогли прочесть массив.
Для подсчета количества одинаковых элементов в каждой строке переберите 2 элемента:
Теперь сортировка. Используйте std::sort.
Что бы не перемещать строки, сортируйте их номера. Заведите массив rows с номерами строк, и сортируйте его, используя специальную функцию сравнения, которая сравнивает не сами числа, а строки с этими номерами: