А почему левая четырехугольная область тут считается внутри многоугольника? Чем она принципиально отличается от правой треугольной, которая помечена как снаружи? По методу луча она тоже будет снаружи.
Смотрите код внимательно. Полуинтервалы, открытые сверху. Не с начала или с конца, а сверху всегда. В первом примере с касанием угла левая грань не будет считаться пересечением, потому что касание идет по верхней точке отрезка, которая исключена. Правая грань так же не зачтется, ибо эта точка верхняя и для второй грани. Если бы касание было нижней точки многоугольника то было бы зачтено 2 пересечения. Точно так же и со вторым примером, там еще есть горизонтальная грань, которая игнорируется всегда.
Будет 1 пересечение. Горизонтальная грань будет проигнорирована вообще. Верхняя грань зачтется за 1 пересечение по вершине. Нижняя грань (внешняя) не будет учтена за пересечение, потому что она лежит на луче верхней точкой. Условие в алгоритме всегда игнорирует верхнюю точку любого отрезка или горизонтальные отрезки целиком.
Этот метод нормально учитывает и если граница полигона касается горизонтального луча сверху или снизу в вершине или по горизонтальному отрезку. В этом случае будет 0 или 2 пересечения, если касание снизу или сверху соответственно. Что и нужно для корректной четности.
Это тоже правильный метод. Надо только аккуратно обрабатывать точку на грани или совпадающую с вершиной многоугольника. Его недостаток — скорость. Медленные тригонометрические функции и невозможность сделать целиком в целых числах.
Метод пересечения с лучом можно реализовать без деления вообще в целых числах, если координаты всех вершин целые.
Нет, не требует. Вы реализовали полностью правильный алгоритм. Грани соседствующие с горизонтальной на луче посчитаются 0, 1 или 2 раза в зависимости от из ориентации. У вас все отрезки закрыты снизу и открыты сверху, обратите внимание на строгие и нестрогие знаки: ((yp <= y and y < yp_prev) or (yp_prev <= y and y < yp)). Поэтому на картинке сверху будет одно пересечение, а если бы касание горизонтальной грани было сверху — то было бы 2 пересечения.
Там же в комментариях приводят решение этой проблемы: https://habrahabr.ru/post/125356/#comment_4125696
Кстати, оно уже применено автором: "(yp <= y and y < yp_prev) or (yp_prev <= y and y < yp)". Все отрезки считаются открытыми сверху и закрытыми снизу. Поэтому пересечения с концами отрезков отрабатываются правильно — как 0, 1 или 2 пересечения с правильной четностью.
На 6:40 на втором видео начинаются какие-то съемки из космоса — это же рендер просто? Типа, как художник представляет себе, что там с ракетой в этот момент происходит?
Все равно, эти ревизоры можно отследить. Он же команды со специального сервера получает. Если есть коннект к контрольному серверу, то заворачиваем трафик на фильтр. Или еще хитрее — делаем простенькое DPI, через то же mitmproxy, к серверу и просто заменяем ответы на нужные соответственно черному списку.
Я считаю матожидание количества символов для одной, заранее заданной строки. А вы считает вероятность того, что одна строка будет раньше другой или частоту вхождения строки в бесконечный поток. И то и другое не является матожиданием количества символов.
Эта программа считает не то — количество вхождений. Оно будет одинаковым.
Вот программа, которая считает то, про что в задаче и спрашивается — https://jsfiddle.net/zwnfft73/4/
Поиграйтесь прямо в браузере — результаты разные.
Если обезьяна уже набрала ЧЧ, я не считаю сколько ей еще надо нажать клавиш чтобы в той же строке набрать ЧК. А вы как раз ЭТО считаете.
А именно это и надо считать.
Измените ваш код для работы только с ОДНОЙ строкой. Мы же считаем как тяжело получить одну строку, именно ту, которую выбрали? Потом запустите этот код для разных строк "чч" и "чк" и вы получите разные результаты.
Вот вы никак не понимаете разницу между вопросами:
1) из двух строк выберете ту, которая встретится раньше в случайном тексте (правильный ответ — неважно)
2) выберете строку так, чтоб для ее печати потребовалось в среднем меньше символов (ответ — "чк" лучше "чч")
На первый взгляд кажется, что если в среднем требуется меньше символов, то и встречаться первый раз строка должна раньше других. Но это не так.
Да из 100 тысяч обезьян примерно половина напечатает сначала "чч" а примерно половина "чк" (если выгонять их когда случится одно из двух). Но если первые 50 тысяч заставить печатать пока они не наберут "чч", а вторые 50 тысяч — пока они не наберут "чк", то первые обезьяны напечатают более длинные тексты.
Проблема в том, что вы проводите другой эксперимент. Вы выгоняете обезьян из-за машинки когда они напечатали или одно или другое. В исходной же задаче обезьяна печатает пока не наберет только одну заданную строку. Этот эксперимент для двух разных строк дает разные результаты.
Да, вероятности встретить сначала "чч" или "чк" одинаковы.
Я не говорил нигде про вероятность получить сначала одно или другое. Я считал среднее количество нажатий.
Кстати, из того, что матожидание одной величины больше матожидания второй величины никак не следует, что первая окажется больше второй в более чем половине случаев.
Проблема в том, что вы считаете количество нажатий до первой встречи строки str1 при том что строка str2 ни разу не встретилась (и наоборот для второй строки). Это совсем другие величины. Можно этот пример довести до абсурда и считать сразу для всех четырех возможных строчек. Тогда цикл while у вас всегда завершится на второй итерации, что, согласитесь, странно. И вы подсчитаете для каждой строки сумму из двоек. Более того у вас при этом ответ не сойдется с текущей вашей программой.
Надо или разделить на 2 параллельных цикла отдельно для str1 и str2, или гнать цикл while пока не встретятся ОБЕ строки, запоминая где первый раз каждая из них попалась.
Почти. Вот если бы вы при каждом новом броске платили 1$, а как-только последние 2 броска совпали с вашей комбинацией, вы получаете 10$ — тогда да — выгоднее ставить на "чк" а не на "чч".
Да, автор эту деталь не описал, хотя в коде она присутствует.
А почему левая четырехугольная область тут считается внутри многоугольника? Чем она принципиально отличается от правой треугольной, которая помечена как снаружи? По методу луча она тоже будет снаружи.
Смотрите код внимательно. Полуинтервалы, открытые сверху. Не с начала или с конца, а сверху всегда. В первом примере с касанием угла левая грань не будет считаться пересечением, потому что касание идет по верхней точке отрезка, которая исключена. Правая грань так же не зачтется, ибо эта точка верхняя и для второй грани. Если бы касание было нижней точки многоугольника то было бы зачтено 2 пересечения. Точно так же и со вторым примером, там еще есть горизонтальная грань, которая игнорируется всегда.
Будет 1 пересечение. Горизонтальная грань будет проигнорирована вообще. Верхняя грань зачтется за 1 пересечение по вершине. Нижняя грань (внешняя) не будет учтена за пересечение, потому что она лежит на луче верхней точкой. Условие в алгоритме всегда игнорирует верхнюю точку любого отрезка или горизонтальные отрезки целиком.
Этот метод нормально учитывает и если граница полигона касается горизонтального луча сверху или снизу в вершине или по горизонтальному отрезку. В этом случае будет 0 или 2 пересечения, если касание снизу или сверху соответственно. Что и нужно для корректной четности.
Первый способ определения полигонов является более логичным. Иначе одно и то же множество точек будет описываться бесконечным количеством полигонов.
Это тоже правильный метод. Надо только аккуратно обрабатывать точку на грани или совпадающую с вершиной многоугольника. Его недостаток — скорость. Медленные тригонометрические функции и невозможность сделать целиком в целых числах.
Метод пересечения с лучом можно реализовать без деления вообще в целых числах, если координаты всех вершин целые.
Нет, не требует. Вы реализовали полностью правильный алгоритм. Грани соседствующие с горизонтальной на луче посчитаются 0, 1 или 2 раза в зависимости от из ориентации. У вас все отрезки закрыты снизу и открыты сверху, обратите внимание на строгие и нестрогие знаки: ((yp <= y and y < yp_prev) or (yp_prev <= y and y < yp)). Поэтому на картинке сверху будет одно пересечение, а если бы касание горизонтальной грани было сверху — то было бы 2 пересечения.
Чем построение выпуклой оболочки поможет определить вхождение точки в многоугольник?
Там же в комментариях приводят решение этой проблемы: https://habrahabr.ru/post/125356/#comment_4125696
Кстати, оно уже применено автором: "(yp <= y and y < yp_prev) or (yp_prev <= y and y < yp)". Все отрезки считаются открытыми сверху и закрытыми снизу. Поэтому пересечения с концами отрезков отрабатываются правильно — как 0, 1 или 2 пересечения с правильной четностью.
Все равно, эти ревизоры можно отследить. Он же команды со специального сервера получает. Если есть коннект к контрольному серверу, то заворачиваем трафик на фильтр. Или еще хитрее — делаем простенькое DPI, через то же mitmproxy, к серверу и просто заменяем ответы на нужные соответственно черному списку.
А где вы там смогли найти заявки и кто получил тендер?
Я считаю матожидание количества символов для одной, заранее заданной строки. А вы считает вероятность того, что одна строка будет раньше другой или частоту вхождения строки в бесконечный поток. И то и другое не является матожиданием количества символов.
Эта программа считает не то — количество вхождений. Оно будет одинаковым.
Вот программа, которая считает то, про что в задаче и спрашивается — https://jsfiddle.net/zwnfft73/4/
Поиграйтесь прямо в браузере — результаты разные.
То же самое, что и выгнать. Вы отбрасываете что бы она дальше ни напечатала.
А именно это и надо считать.
Измените ваш код для работы только с ОДНОЙ строкой. Мы же считаем как тяжело получить одну строку, именно ту, которую выбрали? Потом запустите этот код для разных строк "чч" и "чк" и вы получите разные результаты.
Вот вы никак не понимаете разницу между вопросами:
1) из двух строк выберете ту, которая встретится раньше в случайном тексте (правильный ответ — неважно)
2) выберете строку так, чтоб для ее печати потребовалось в среднем меньше символов (ответ — "чк" лучше "чч")
На первый взгляд кажется, что если в среднем требуется меньше символов, то и встречаться первый раз строка должна раньше других. Но это не так.
Да из 100 тысяч обезьян примерно половина напечатает сначала "чч" а примерно половина "чк" (если выгонять их когда случится одно из двух). Но если первые 50 тысяч заставить печатать пока они не наберут "чч", а вторые 50 тысяч — пока они не наберут "чк", то первые обезьяны напечатают более длинные тексты.
Проблема в том, что вы проводите другой эксперимент. Вы выгоняете обезьян из-за машинки когда они напечатали или одно или другое. В исходной же задаче обезьяна печатает пока не наберет только одну заданную строку. Этот эксперимент для двух разных строк дает разные результаты.
Да, вероятности встретить сначала "чч" или "чк" одинаковы.
Я не говорил нигде про вероятность получить сначала одно или другое. Я считал среднее количество нажатий.
Кстати, из того, что матожидание одной величины больше матожидания второй величины никак не следует, что первая окажется больше второй в более чем половине случаев.
Проблема в том, что вы считаете количество нажатий до первой встречи строки str1 при том что строка str2 ни разу не встретилась (и наоборот для второй строки). Это совсем другие величины. Можно этот пример довести до абсурда и считать сразу для всех четырех возможных строчек. Тогда цикл while у вас всегда завершится на второй итерации, что, согласитесь, странно. И вы подсчитаете для каждой строки сумму из двоек. Более того у вас при этом ответ не сойдется с текущей вашей программой.
Надо или разделить на 2 параллельных цикла отдельно для str1 и str2, или гнать цикл while пока не встретятся ОБЕ строки, запоминая где первый раз каждая из них попалась.
Почти. Вот если бы вы при каждом новом броске платили 1$, а как-только последние 2 броска совпали с вашей комбинацией, вы получаете 10$ — тогда да — выгоднее ставить на "чк" а не на "чч".