• Почему неправильно работает такая реализация алгоритма быстрой сортировки?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    тут много проблем.

    1) не надо в конце part менять местами 0-ой и i-ый элементы. Это бессмысленно. Вы поддерживаете вариант, что элементы с 0 по i-ый <=x, c j-ого и дальше >=x

    2) У вас у part() параметр m передается по значению. Изменение его в конце функции не видно из места вызова. Вы каждый раз, независимо от того, как разбиение произошло, рекурсивно запускаетесь половин массива разделенных ровно по середине.

    3) Что у вас с рекурсивными вызовами твориться? Вы хвостовую рекурсию руками схлопнули что ли? А зачем выбирать, с какой стороны рекурсивно вызваться, а с какую дальше в цикле обрабатывать? Там у вас что-то с вычислениями напутанно, всякие +-1 неверно распиханы. Вы там делаете k -= left+1 и k -= right+1. По логике в одной половине left элементов, в другой - right. Тогда почему вы -1 еще делаете и там и там?
    Ответ написан
  • Как решить задачу на C++ быстрее чем за n^2?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Есть за O(n log m) решение, но оно технически сложноватое. Реализуется через балансированное бинарное дерево поиска с неявным ключем. Грубо говоря, если в каждой вершине балансированного дерева хранить сколько всего вершин в поддереве, то в такой структуре можно искать вершину по номеру. Можно так же в это дерево вставлять вершину на заданную позицию.

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

    При шифровании, получив число, вы по указателю находите, где вершина в дереве. Поднимаясь вверх, проверяя из правого или левого поддерева вы пришли можно подсчитать какая ваша начальная вершина в дереве по счету. Это число и выводите в ответ. Потом удаляете вершину из дерева и вствляете в начало.

    При расшифровке - прочитанное число указывает на порядковый номер вершины в дереве. Находите вершину, ее значение пишите в ответ, удаляете вершину и добавляете в начало.

    Edit: тут было неправильное решение через недо-skip-list.

    Есть чуть более простое в реализации решение, но на той же идее. Вместо бинарного дерева поиска используйте дерево отрезков.

    Заведите отрезок на n+m элементов. Кадому символу в алфавите будет соответствовать еденица где-то в этом отрезке. Изначально они занимают n самых правых позиций. Их порядок - это будет та самая перестановка из условия. Дервево отрезков будет считать сумму. В таком дереве можно за логарифм найти k-ую еденицу (рекурсивный спуск) и узнать какой по порядку является данная еденица (запрос на сумму на отрезке 0..i-1). Еще для каждого символа алфавита храните, где именно на отрезке лежит соответствующая ему еденица, а для каждого элемента на отрезке, какому символу он соответствует.

    При шифровании вы находите еденицу для символа алфавита, считаете какая она по порядку и выводите это число. потом перемещаете эту еденицу левее всех едениц. Это делается просто - на i-ой операции надо втыкать еденицу в позицию m-i+1.

    При дешифровании вы находите к-ую еденицу, выводите соответствующий ей символ и перемещаете еденицу левее остальных.
    Ответ написан
  • Где у меня может быть ошибка в нахождении площади сложной фигуры?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Не совсем понятен ваш код слияния двух массивов отрезков. Я бы все промежуточные точки тупо загнал в один вектор и отсортировал. Ну или сделал стандартное слияние двух отсортированных массивов. Дальше в цикле считал бы на отрезке между двумя соседними точками (если длина отрезка хотя бы 1e-6), Параметры кривых ищутся легко - держите 2 счетчика, как у вас уже есть, и двигайте их, пока текущий отрезок для той или иной функции не станет закрываться позже начала текущего отрезка. Может ваш код и эквивалентен этому, но я в этом не уверен.

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

    Еще, очевидная проблема вот: comp_a != 0. Флоаты нельзя никогда сравнивать точно. Только с епсилон:
    x < y  ====> x < y - eps
    x <= y ====> x < y + eps 
    x == y ====> fabs(x-y) < eps
    x != y ====> fabs(x-y) > eps
    Ответ написан
  • Количество комбинаций чисел JavaScript?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    В тупую можно подсчитать 2-мя вложенными циклами.

    ans = 0;
    for (i = 1; i <= 3; ++i) {
      for (j = 1; j <= 3; ++j) {
        mn = max(n - i - j - 3, 1);
        mx = n - i - j - 1;
        if (mn <= mx)
          ans += mx - mn + 1;
      }
    }


    Работает так - перебираем сколько символов в первом и втором блоке. После этого считаем, сколько минимально и максимально может быть символов в третьем блоке (оставляя на последний от 1 до 3 символов). Прибавляем к ответу количество возможных вариантов для длины третьего блока.

    Но это если у вас параметры фиксированные (4 блока 1-3 символа). Если параметры могут меняться, то решение - динамическое программирование f(i,k) - сколько способов разбить первые i символов на k блоков.

    База: f(0,0) = 1, f(0, k>0) = 0, f (i>0, 0) = 0;
    Пересчет: f(i,k) = sum_{l=min_length...min(max_length, i)}(f(i-l,k-1)).
    Ответ: f(n, num_blocks).
    Ответ написан
    Комментировать
  • Как найти повторяющиеся элементы в разных коллекциях за линейное время?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Это задача на поиск компонент связности в графе. У вас двудольный граф, но это не важно. Вершины - емейлы и пользователи, ребра - соответствие пользователя емейлу. Решается обходом в глубину или обходом в ширину. Оба решения - линейные от количества ребер (в вашем случае - общее количество емейлов).

    Перенумеруйте все емейлы и всех пользователей.
    Код будет проще, если емейлы и пользователи хранятся в одном и том же пространстве номеров.
    Это реализуется с одним hashMap, который будет давать номер по строке, и одним массивом строк, который будет хранить изначальную строку по номеру. Вам еще понадобится булевый массив, чтобы хранить, является ли данная вершина пользователем или мейлом. При вводе получаете какую-то строку, и вызываете от нее функцию GetID(s, is_user), которая проверяет, есть ли данная строка в мапе. Если есть, возвращает номер. Если нет - дописывает строку в массив строк, записывает ее индекс в мап и возвращает его.

    При вводе - постройте граф.
    Храните ребра в списке смежности - массив массивов или списков, где для каждого номера-вершины вы построите список всех с ней связанных.
    При вводе у вас есть номер вершины-пользователя и вы читаете емейлы и переводите их номера. При этом добавляйте номер-емейл в список для пользователя и наоборот.

    Заведите массив пометок "обойденности" для всех вершин. Он будет int. 0 - непосещенные вершины, иначе номер компоненты связности.
    Запустите на этом графе DFS/BFS от каждой пока не обойденной вершины в цикле и помечайте все достижимые вершины новым числом (можно передавать вторым параметром в DFS). Можно сразу же во время обхода заполнять структуру ответ - один номер для пользователя и список для емейлов. Или можно после цикла с DFS завести массив списков для ответа, пройтись по массиву и распихать номера вершин по спискам. Используйте булевый массив, чтобы понять какая вершина пользователь, а какая - мейл. Из пользователей возьмите только одного предстваителя, а все емейлы запихайте в список в ответ. Потом выводите, преобразуя номера в строки с помощью имеющегося массива.
    Ответ написан
    1 комментарий
  • Как выловить ошибку в коде?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Похоже, на строке "abcdef" у вас выдаст d=0, а может и вообще d не напишет.

    Проблема в том, что вы пытаетесь считать параллельно для правой и левой половины. Логично, коэффициенты там симметричные будут, но можно сделать ошибку. И ускорения ваша оптимизация практически не несет. В 2 раза меньше итераций, делающих в 2 раза больше + дополнительная проверка каждый раз. На компилируемых языках может быть еще и медленнее наивного цикла от 0 до n-1. В питоне - не знаю. Уж точно не в 2 раза быстрее, как можно было бы подумать.

    Еще, я бы вместо последовательного обновления коэффициента в previous считал его явно. i-ый символ встречается ровно в (i+1)*(n-i) подстроках.
    Ответ написан
    1 комментарий
  • Как быстро найти зависимость элементов в последовательном ряду?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Если зависимость может быть любая (например, числа фиббоначи) - то никак. Можно поискать последовательность на oeis.org

    Если же возможна только зависимость вида +a_0, +a_1, +a_2,..., +a_k, +a_0, +a_1... т.е. повторяющийся фиксированный паттерн приращений, то есть быстрое и простое решение.

    Во первых, если вам дано 10 чисел, то всегда можно сказать, что есть паттерн длиной в 9 приращений.
    Но можно найти кратчайший паттерн с помощью алгоритма поиска периода в строке. Буквально, по определению, нужный вам кратчайший паттерн (типа {+3, -2} для второго примера) будет периодом строки. Правда, тут не строка, а массив чисел, но это вообще никак не меняет алгоритмы. Просто у вас алфавит нестандартный.

    Сначала от массива чисел перейдите к массиву приращений.

    Потом можно применить жадное наивное решение - просто перебираете все возможные значения периода от 1 до n/2 и проверяете, что a[i] == a[i+str] для всех i. Как только все совпало - вы нашли период. Это решение за квадрат. Если чисел вам задано много, то можно применить префикс функцию: найдите значение префикс функции (p) для всей строки и, если ее значение больше половины длины строки, то у строки есть период n-p. Это будет линейное решение.

    Еще можно применить алгоритм Дюваля. Тоже линейное решение, но более сложное в реализации и понимании.
    Ответ написан
    4 комментария
  • Почему в d-ичном куче ребёнок выисляется по такой формуле?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Удобнее, если нумеровать вершины с 0. Тогда дети будут d*i+1...d*i+d. Ваша формула получается из этой простым перенумерованием (вычитанием и добавлением единицы в нужные места). Далее я буду рассуждать об этой формуле.

    В этой формуле очевидно, что отцом у вершины k (с номером > 0) будет floor((k-1)/d). Далее, видно, что для двух разных вершин номера их детей не будут пересекаться никак (потому что это отрезки из d номеров, сдвинутые как минимум на d относительно друг друга). Так же можно доказать по индукции, что все числа от 1 до бесконечности будут соответсвовать какой-то вершине в дереве (мы же можем получить отца по формуле (x-1)/d, по индукции он уже в дереве, а значит и текущий номер соответствует вершине).

    Интитивно же, умножение на d появляется потому, что на каждом следующем уровне вершин ровно в d раз больше чем на предыдущем. Все дети одной вершины идут подряд, значит будут в формуле +1,+2... для детей.
    Ответ написан
  • Предложение алгоритма решения тестового задания?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Ваше решение не работает на примере "аб аа".

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

    Но в ваше решение еще не рассматривает крайний случай - использованы все 33 буквы алфавита и есть надо что-то менять. Тут ответ 0, потому что замены делать никак не получится - после любой замены 2 разные типа букв станут одинаковыми и перемешаются. Разделить их после этого уже не получится.

    Если вы эти косяки исправите, ваше решение может не пройти по времени, потому что оно у вас за квадрат. Лучшее решение - пройтись по строкам одновременно одним циклом и запоминать в массиве, индексированном символами, (или мапе), какая буква алфавита во втором слове соответствует букве алфавита в первом слове. Если встречаете противоречие (в массиве уже что-то записано не такое как вы видите сейчас), то ответ 0.

    И еще. Не надо разбивать строки через .split(''). В JavaScript можно узнать длину строк и обратиться к i-ому символу не преобразуя в массив.
    Ответ написан
    Комментировать
  • Как применить бинарный поиск к массиву строк на Пайтон??

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Не понимаю, в чем проблема вообще. Забудьте, что это строки или числа. Все что нужно для бинпоиска - это уметь спрашивать < или = искомая штука и штука в массиве по заданной позиции.

    В питоне есть массивы (доступ по индексу) и строки он сравнивает автоматом через операторы == и <.

    Т.е. можно написать тот же абсолютно код, что и для бинпоиска по числам и он будет работать на строках. Правда, надо помнить, что сложность у бинпоиска по строкам будет не O(log n), а O(L log n), где L - максимальная длина строк.
    Ответ написан
    2 комментария
  • Как решить данную задачу по курсовой на языке С++?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Вам ДАНА матрица. Значит в программе надо
    1) прочитать числа N и M (заведите 2 переменные и прочитайте их, через cin)
    2) Завести N*M матрицу. В C++ стандартом для массивов является класс vector. Двумерный массив - это вектор векторов.
    vector<vector<int>> a(n);
    Это создаст вектор из n векторов, но они все будут пустые. Надо во время считывания ( у вас будет 2 вложенных цикла) перед считыванием i-ой строки i-ый вектор отресайзить вызвав a[i].resize(m). И далее можно будет читать a[i][j]
    3) Теперь, собственно, алгоритм. Найдите наибольший элемент. Для этого заведите 3 переменные - текущий максимум (можно инициализировать a[0][0]) и его координаты mx и my (инициализируйте нулями). Пройдитесь по матрице двумя вложенными циклами и, если текущий элемент больше максимума - перезапишите максимум и запомните текущие переменные циклов в mx и my.
    4) Теперь поменяйте местами 0-ую строку со строкой в которой максимум. Для этого одним циклом пройдитесь по столбцам (от 0 до M-1) и поменяйте местами a[0][j] и a[mx][j].
    5) Теперь то же самое, но по столбцам. Цикл от 0 до N-1 и меняйте элементы a[i][0] и a[i][my].
    6) В конце выведите матрицу двумя вложенными циклами.

    Для смены двух значений нужна временная перменная, например tmp.
    Ответ написан
    1 комментарий
  • Как вывести всплывающее окно на всех сайтах находящихся в подпапках?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Если все сайты не подключают какой-то один и тот же скрипт/шаблон, то единственный вариант - это обойти все папки и добавить код куда надо (в html шаблон или какой-то js файл, я хз, как ваша cms устроена).

    Если такой файл есть, то допишите код окна туда. Если cms одна и та же и сайты сделаны однообразно, то есть надежда, что такой файл существует. Можно вообще извратиться (если решение временное), вдруг у вас один и тот же условный /jquery.js подключатся во всех подпапках. Вот в него и впихивайте хоть alert(), хоть dom-манипуляцию.

    Если же в каждой папке полностью независимая копия, то - увы.

    Раз все cms одинаковые, то, скорее всего, есть какой-то одинаково называющийся файл во всех, в который код окна и можно добавить. Но не обязательно это делать руками N раз.

    Все эти файлы надо найти каким-то скриптом, а потом как-то в них вставить код.
    Если на линухе, то можно файлы найти аж так - передайте "./*/some-fixed-path/file-we-need.js" в качестве параметра в скрипт и bash сам раскроет шаблон и найдет все файлы. А скрипт может вызывать тупо patch < diff.txt. Вы руками внесите изменения в один файл, сделайте diff, и его результат скармливайте patch. Если изменения можно внести в одно и то же место во всех файлах (в самое, начало, например), то все сработает без ошибок. Читайте man diff, man patch. Еще можно man find.
    Ответ написан
    1 комментарий
  • Формат файла описывающий действия?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Файл, похоже, в формате json. Гуглите "json <ваш язык прогаммирования>", чтобы найти библиотеку для парсинга этого формата. Потом надо обрабатывать семантику языка.

    Поля "$designer" похоже можно игнорировать. Дальше у каждого важного элемента есть поле "$kind". Читайте описание в схеме, которая по ссылке в конце файла "https://raw.githubusercontent.com/microsoft/BotFra..."

    Фактически это задана программа на весьма неудобном для человека языке программирования. Каждое действие - это узел в json. Он имеет kind, который определяет, что это за инструкция и всякие дополнительные поля, которые описывают параметры этой инструкции. Типа инструкция ветвления содержит команды для обеих веток исполнения и условие. В этом языке, похоже есть циклы, встроенные функции. Похоже, пользователь может задать какие-то свои функции, вызов которых вам тоже придется обрабатывать.

    После разбора файла json-парсером, надо писать обработку каждого типа действия, которое есть в этом файле. Это будет полноценный интерпретатор этого странного языка программирования.

    Например, "Microsoft.ForEach". Поищите эту строчку в схеме, она будет встречаться 6 раз. Интересное место №3 - там расписано, какие поля могут быть у этого типа действия. Там куча очевидных полей вроде designer и kind, но есть нужное нам "actions". Описание говорит, что это массив действий, которые будут вызваны для всех элементов списка. Т.е. встретив в файле узел foreach, надо взять поле "actions" и применить все действия оттуда ко всем элементам входного списка.

    И так надо по каждому "kind" действия писать обработку. Проще всего его будет писать на каком-то интерпретируемом языке, где есть что-то типа eval(). Потому что, например, в IfCondition есть поле condition, которое придется вычислять. Надо будет поддерживать какой-то словарь для всех переменных, локальных и глобальных, поддерживать стек вызова и словарь всех известных пользовательских подпрограм.
    Ответ написан
    3 комментария
  • Подходит простой язык программирования как первый?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Можно начинать с более простого. Конечно, лучше сразу изучить что-то более распространенное, но если вам не заходит, то набейте руку сначала на простом языке.
    Ответ написан
    Комментировать
  • Как исправить Tl?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Попробуйте читать через scanf.

    Я вижу, вы делаете через sync_with_stdio(0), но я не уверен, что это 100% помогает.

    Потом, вместо set vis достаточно передавать в dfs предыдущую вершину и не ходить в нее.

    А еше у вас ошибка, при делении ребра пополам нельзя делить пополам cnt*w. Если cnt четное, а w нечетное, вы потереяете округление. Надо пихать в кучу пару cnt, w, и брать максимальное cnt*ceil(w/2). И еще, вы пихаете в кучу цену ребра, помноженную на количество листьев по этому ребру и всем предыдущем в текущей вершине! Надо там не cur брать, а значение dfs.

    И еще, оно скорее всего виснет из-за переполнения. При умножении cur*c.second может получиться отрицательное число, вы же int-ы перемножаете, и только потом к long long приводите.
    Ответ написан
    Комментировать
  • Какие есть варианты получить все свойства многомерного массива?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    У вас, фактически, задано дерево. Каждая вершина - это элемент на каком-то уровне в массиве. Его свойство SUB - это дети дерева.

    Вам надо получить список всех вершин, т.е. обойти дерево. Тут есть 2 стандартных решения - обход в ширину и обход в глубину. В глубину - это рекурсивная функция. В ширину, это будет итеративное решение, но нужна очередь.

    Рекурсивное решение пишется легче всего, как мне кажется.
    Ответ написан
    Комментировать
  • Как построить уравнение эллипса с заданным центром, который касается двух заданных отрезков в заданных точках?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Во-первых, перенесите центр системы координат в центр элипса - вычтите его из всех координат точек касания. В самом конце надо будет сделать обратный переход и подставить x=x-x0, y=y-y0 в уравнение.

    При выборе правильной системы координат, эллипс становится окружностью, ведь его уравнение x^2/a^2+y^2/b^2=1. Все остальное - это от переноса центра координат и поворота эллипса.

    Давайте переобразуем нашу систему координат, повернув на какой-то угол и сжав вдоль оси X, чтобы получить круг.

    с- cos(угол), s=sin(угол) k- коэффициент сжатия.

    Тогда новая система координат - {kc,ks}, {s,-c}. Преобразуем в эту систему координат тички касания и вектора касательных. Они так и останутся касающимися нашего эллипса, ведь преобразования поворота и сжатия оставит прямые прямыми, а эллипс - эллипсом (или кругом).

    Если x1,y1 - точка касания, а {xv, yv} - вектор касательной, то:

    x1' = x1*kc+y1*ks

    y1' = x1*s-y1*c

    xv' = xv*kc+yv*ks

    yv' = xv*s-yv*c

    Это просто формулы перобразования между системами координат. Аналогично можно сделать для x2', y2', xw,' yw'.

    Теперь составим уравнения. Мы же хотим найти преобразование, в котором наш эллипс будет окружностью. Во-первых, расстояния до точек касания должны быть одинаковыми. Во-вторых, касательные вектора должны быть перпендикулярны векторам из начала координат к точкам касания.

    Если аккуратно расписать x1'*x1'+y1'*y1'-x2'*x2'-y2'*y2' = 0, и заменить c^2=1-s^2, то будет:

    (y1*y1-y2*y2-x1*x1+x2*x2)*kkss + (2*x1*y1-2*x2*y2)kkcs + (x1*x1-x2*x2-y1*y1+y2*y2)ss +(2*x2*y2-2*x1*y1)*cs +(x1*x1-x2*x2)*kk+(y1*y1-y2*y2)=0

    Советую не верить мне тут с коэффициентами, а пепроверить их самостоятельно.

    Аналогичные уравнения для касательных x1'*xv'+y1'*yv' = 0:
    (y1*yv-x1*xv)*kkss + (x1*yv+y1*xv)kkcs + (x1*xv-y1*yv)ss +(-x1*yv-y1*xv)*cs +(x1*xv)*kk-y1*yv=0

    Важно заметить, что у нас тут 3 уравнения вида:

    A*kkss+B*kkcs-Ass-Bcs+Ckk+D=0, где константые коэффициенты A,B,C,D (разные в трех уравнениях) и 3 переменные k,s,c. Еще есть дополнительное условие s*s+c*c=1, это же синусы/косинусы угла, и k!=0. k может быть и отрицательным, это означало бы отражение и сжатие системы координат. Под наши цели подходит.

    Обратите внимание, 3-е и 4-ое слагаемые идут с теми же коээфициентами, что и 1-е и 2-е, но с обратными знаками. Можно подобрать такие коээфициенты для первых двух уравнений, что если их прибавить к тертьему уравнению, то коэффициенты перед kkss,kkcs,ss,cs - все станут равны нулю. Это надо решить систему из двух линейных уравнений.
    Пусть коээфициенты в уравнениях A1,A2,A3,B1,B2,B3,C1 и т.д. (напоминаю, это константы, вычеслимые через заданные координаты точек и векторов касания). Введем 2 переменные x, y - коээфециенты, с какими прибавлять первые 2 уравнения к тертьему. Условия: A1*x+A2*y+A3=0, B1*x+B2*y+B3=0. Решив эту систему уравнений, найдя коээфициенты и прибавив первые 2 уравнения к тертьему, вы получите уравнение вида

    C4*k*k+D4=0

    Элементарно решив его, вы найдете k. Подставив его в 2 предыдущих уравнения вы получите 2 уравнения вида:

    A4*ss+B4*cs + D4 = 0

    Это тригонометрическое уравнение можно решить, дописав множитель cc+ss к D4, получив уравнение вида:

    (A4+D4)*ss+B5*cs+D4*cc = 0.

    Теперь осталось поделить обе части на с^2 и решить квадратное уровнение для tan(). Еще, правда, надо рассмотреть подходит ли c=0,s=1 (s=-1 рассматривать не надо, Ведь без разницы, в какую сторону вращать на 90 градусов - все равно ось сжатия будет одна и та же).

    Теперь зная тангенс найдите косинус и синус (школьные тригонометрические формулы, вроде c=sqrt(1/(1+t^2)).

    Все, мы знаем k,c,s. Подставив их в формулы для x1',y1' мы узнаем радиус окрудности (расстояние до нуля). Пусть радиус будет r.

    Теперь уравнение эллипса x'^2+y'^2 = r^2.

    Подставляем преобразование:

    x'=x*k*s+y*k*c, y' = x*s-y*c. Потом не забываем сделать замену x<-x-x0, y<-y-y0, чтобы верунть центр эллипса в заданное место.

    Все эти замены надо аккуратно подставить и раскрыть скобки в уравнении x'^2+y'^2 = r^2 и получить ваши коээфициенты в уравнении Ax2+ Bxy + Cy2 + Dx + Ey = F. Потом поделите обе части на F.

    Это решение невозможно расписать аналитически на бумаге до конца, потому что слишком много подставлений и этапов - будут просто монсрячные формулы. Но, в алгоритме, делая по шагам, вводя переменные и коэффициенты это не сложно сделать.

    Edit:

    Тут есть потенциальная проблема - надо решить систему линейных уравнений и 2 квадратных уравнения в процессе решения. Я не могу доказать, но верю всей душой, что, если эллипс существует, то все эти уравнения будут решатся в вещественных числах, без делений на 0 и квадратных корней из отрицательных чисел.
    Ответ написан
    7 комментариев
  • Почему группа Шоттки выглядит неправильно?

    wataru
    @wataru Куратор тега Математика
    Разработчик на С++, экс-олимпиадник.
    Из обсуждения под вопросом стало понятно, что нужно, чтобы окружности в узоре касались, т.е. образовывали связную структуру. Для этого надо, во первых, чтобы исходные окружности касались и, во вторых, чтобы преобразование оставляло точки касания на месте. Можно подобрать множество таких преобразований, но подойдет например преобразование инверсии, которое оставляет на месте сами окружности целиком.
    Ответ написан
    Комментировать
  • Комбинаторика в Java Script, как добавить точку во всех возможных комбинациях массива?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Делайте рекурсивную функцию, которая решает вашу задачу. Если символ на входе 1 - просто его и возвращает. Если входных символов несколько - то откусывает последний символ и вызывается рекурсивно, потом к возвращенному массиву к каждому элементу дописывает последний символ и точку-последний символ (новый массив с удвоенным количеством элементов).

    Так для 3 символов "abc" будет вызвана функция для "ab", которая вернет [ab, a.b], дописав "c" и ".c" к каждому элементу мы получим [abc, ab.c, a.bc, a.b.c].
    Ответ написан
  • Почему при сериализации uint128 сначала сериализуют hi, потом lo, а не наоборот?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Почему сериализуют так а не наоборот? Просто так принято при передаче по сети. Сериализация может использоваться и для этого, поэтому автор, наверно, сделал так.

    На самом деле - можно делать как автору библиотеки захочется. Хоть сначала все четные биты записать, потом - нечетные, хоть hi/low, хоть Low/hi, если какая-то совместимость с другими библиотеками не требуется.
    Ответ написан
    6 комментариев