REASY Думаю, вариант с "нижней + левой" точками неверен. Вот пример: Мы включили в Контур точки 1 и 2 - это верно. Далее, мы ведь ищем следующую "самую нижнюю" точку после [2], верно? Это у нас [1]. Левее неё нет ничего. Берём следующую "нижнюю". Тут их аж три. Пойдём по возрастанию - пусть первой будет [3]. И какая же для неё самая левая? Несомненно, [6]. В итоге мы забываем про [7].
А алгоритм мой для определения полуплоскости, в которой лежит точка относительно вектора, вычисляет не что иное как скалярное произведение двух векторов: Первый из них - с началом в точке A(X1, Y1) и концом в C(X3, Y3). Второй же - это _не_ сам вектор AB!! Это всего лишь перпендикуляр к нему, опущенный по правую сторону (т.е. если посмотреть на наш AB так чтобы он указывал строго вверх, то полученный AB' окажется направлен строго вправо). Для пущей понятности немного теории: Скалярное произведение двух векторов в не-координатной геометрии есть произведение модулей векторов на косинус угла между ними. Так вот, нам важен косинус. Как известно, если угол меньше 90°, то косинус положителен. Если же он больше - отрицателен. Равен? - тогда cos = 0. На этом мы и сыграем: введём нормаль AB' к вектору AB (координаты B' должны быть равны: X = Y2; Y = -X2). Если вектор АС лежит в правой полуплоскости, то угол между ним и "правой" нормалью будет <90° - ему просто деваться некуда =) СПВ в координатной плоскости определяется как (X1*X2) + (Y1*Y2), приводя к результатам, аналогичным |V1|*|V2|*cos. С учётом того, что у нас один из векторов - это нормаль, а также из того, что нужно сместить нуль координат в [X1; Y1], имеем: (Y2-Y1)*(X3-X1) + (-1*[X2-X1])*(Y3-Y1) = (Y2-Y1)*(X3-X1) + (X2-X1)*(-1*[Y3-Y1]) = (Y2-Y1)*(X3-X1) + (X2-X1)*(Y1-Y3) Затем мы анализируем знак суммы. Если сумма >0, значит полуплоскость таки правая. Возвращаем 2. Если меньше - левая. Возвращаем 1. Если лежит на продолжении вектора - возвращаем 0. ЗЫ. Чёрт. Во блин что значит температура. Право и лево перепутал =( Всё, уже поправил. Однако если вы это читали до времени последнего редактирования, знайте: где было право - стало лево %) Ещё раз простите. Надо было сразу жаропонижающее пить...
REASY тогда в твоём первоначальном коде можно придраться разве только к отсутствию проверок на недопустимость символов и оптимизации программы, но вроде ни то ни другое не требовалось. Если всё-же захочешь разобраться с битовым вариантом, то вот: правда из-за кривизны консоли текстовка на английском (SetConsoleOutputCP не помогла, а с CharToOem связываться неохота), но комменты имхо достаточно подробные. Code (Text): // Имитация передачи и приёма с сэмплированием для устранения помех #include "stdafx.h" #include <iostream> #include <string> #include <stdlib.h> using namespace std; int main(int argc, char **argv) { string str_kb_in; // Строка с передаваемыми данными введёнными с клавиатуры int k; // Коэффициент сэмплирования cout << "k = "; cin >> k; // Проверка k на чётность и исправление если не так if (k % 2 == 0) { k++; cout << "Not even k correct to k = " << k << '\n'; } // Ввод передаваемой строки (допустимы любые символы кроме пробела (дефект cin)) cout << "Input text for transmit: \n"; cin >> str_kb_in; int len_kb = str_kb_in.length(); int i, b, m; // счётчики // Вывод битового представления текста (не очень красиво но для примера сойдёт ;) // все биты по очереди сдвигаются в младший и "лишние" (все кроме младшего) обнуляются по маске cout << "\nThe bin format of this text: \n"; for (i = 0; i < len_kb; i++) for (b = 7; b >= 0; b--) cout << ((str_kb_in[i] >> b) & 0x1); cout << '\n'; // Подготовка к передаче повтором битов k раз string str_in_receiver = ""; // битовая строка подготовленная для передачи int cb = 0; // счётчик бит в str_in_receiver char currernt_char = 0 ; // текущий символ для str_in_receiver for (i = 0; i < len_kb; i++) // счётчик символов в строке for (b = 7; b >= 0; b--) // счётчик бит в байте for (m = 0; m < k; m++) // счётчик повторов (сэмплов) { currernt_char = (currernt_char << 1) | ((str_kb_in[i] >> b) & 0x1); if (++cb > 7) { cb = 0; str_in_receiver += currernt_char; currernt_char = 0; } } // коррекция "хвоста" (заполнение нулями) if (cb != 0) str_in_receiver += currernt_char << (8 - cb); // потом лишние нули игнорируется поскольку приёмник возьмёт только кратное k количество бит, // но они нужны при хранении битовой строки в символьном массиве string cout << '\n'; // Вывод передаваемой битовой строки (не очень красиво но для примера сойдёт ;) cout << "The transmit format of this text in bin format: \n"; int len_transmit = str_in_receiver.length(); for (i = 0; i < len_transmit; i++) for (b = 7; b >= 0; b--) cout << ((str_in_receiver[i] >> b) & 0x1), '\n'; cout << '\n'; // Генерируем случайный шум и портим им данные int level_noise; // Запрос уровня шума на линии cout << "===============================================\n"; cout << "Input level noise (1 - Lo, 2 - Medium, 3 - Hi):\n"; cin >> level_noise; len_transmit = str_in_receiver.length(); for (i = 0; i < len_transmit; i++) { switch(level_noise) { case 1: // слабый шум // случайное добавление 1 str_in_receiver[i] |= ((rand() * 255 / RAND_MAX)&(rand() * 255 / RAND_MAX)&(rand() * 255 / RAND_MAX)&(rand() * 255 / RAND_MAX)); // случайное добавление 0 str_in_receiver[i] &= ((rand() * 255 / RAND_MAX)|(rand() * 255 / RAND_MAX)|(rand() * 255 / RAND_MAX)|(rand() * 255 / RAND_MAX)); break; case 2: // средний шум - нужно больше повторов // случайное добавление 1 str_in_receiver[i] |= ((rand() * 255 / RAND_MAX)&(rand() * 255 / RAND_MAX)&(rand() * 255 / RAND_MAX)); // случайное добавление 0 str_in_receiver[i] &= ((rand() * 255 / RAND_MAX)|(rand() * 255 / RAND_MAX)|(rand() * 255 / RAND_MAX)); break; default: // сильный шум - нужно много повторов // случайное добавление 1 str_in_receiver[i] |= ((rand() * 255 / RAND_MAX)&(rand() * 255 / RAND_MAX)); // случайное добавление 0 str_in_receiver[i] &= ((rand() * 255 / RAND_MAX)|(rand() * 255 / RAND_MAX)); } } // Вывод принятой битовой строки содержащей смесь шума и данных cout << "\nThe received bin data & noise: \n"; len_transmit = str_in_receiver.length(); for (i = 0; i < len_transmit; i++) for (b = 7; b >= 0; b--) cout << ((str_in_receiver[i] >> b) & 0x1), '\n'; cout << '\n'; // ====== наконец добрались до анализа принимаемых данных ======= // считаем что длина передаваемой строки нам известна (как правило в реальных задачах так оно и есть) // Берём очередной символ в принятой строке // начиная со старшего бита прогоняем блоки по k бит // суммируем биты, проверяем сумму на больше чем k / 2 (целочисленно) // добавляем в символы выходной строки биты от старшего к младшему // если счётчик k прогонов перешагнул 8 бит переходим к следующему символу в строке str_in_receiver string str_result = ""; cb = 7; // счётчик бит int p = 0; // указатель в строке str_in_receiver (уже с шумами) currernt_char = 0; // текущий символ int bit_state = 0; // состояние принимаемого бита (счётчик) for (i = 0; i < len_kb; i++) // счётчик символов в строке str_result { for (b = 7; b >= 0; b--) // счётчик бит в байте для str_result { for (m = 0; m < k; m++) // счётчик повторов (сэмплов) { // считаем количество единиц в блоке из k бит bit_state += ((str_in_receiver[p] >> cb) & 0x1); if (--cb < 0) // переход к следующему символу в str_in_receiver { ++p; cb = 7; } } // помещаем в младший бит 1 если bit_state > (k / 2) или 0 если bit_state < (k / 2) // равенство исключается нечётностью k if (bit_state > (k >> 1)) // здесь k >> 1 = k / 2 (целочисленно) currernt_char |= 1 << b; // ноль помещать не обязательно он там и так есть :) // а 1 "угоняем" в старшие биты насколько нужно bit_state = 0; // очищаем счётчик для следующих бит } str_result += currernt_char; currernt_char = 0; } // хвост с нолями и помехами остаётся нерассмотренным за ненадобностью ;) cout << "\nThe result of transmit & received (bin format): \n"; for (i = 0; i < len_kb; i++) for (b = 7; b >= 0; b--) cout << ((str_result[i] >> b) & 0x1); cout << '\n'; cout << "\nThe result of transmit & received (text format): \n"; cout << str_result << '\n'; // cin >> currernt_char; // чтобы не закрывалась сразу в релиз версии return 0; } Релиз на всякий случай прицепил.
Y_Mur Низзя в таких задачах ничего лишнего на консоль выдавать. При первом же милом приглашении вида программа проверки пошлет кодера вместе с его программой на все три. Если исходник набирать в кодировке DOS (например выставить шрифт Terminal в настройках IDE), то на консоль выводится в том же виде, что и в исходнике. Ну я бы вообще отказался от всей этой ООП-шной бредятины вида +='0'. Использовал бы printf/scanf вместо cout/cin. А буфер для строки выделил бы заранее. Т.е. в виде char inputStr[10001]. Возможно на проверяющей стороне проблемы с выделением/перевыделением/передовыделением памяти в рантайме (подозрение, что пятый тест - тест на 10000 символов в строке). Разумеется, не факт, что поможет, но ИМХО попробовать очень даже стоит.
File 1.txt: ``` #/usr/bin/perl print "9999\n"; print "100"x3333; ``` perl 1.txt | "4.Передача информации.exe" 9999 0 Вроде быстро считает
Y_Mur Спасибо большое, очень интересный пример. Теперь лучше понимается, что по проводам не символы '1','0' передаются, а биты ^^
Насчет этого Вот более подробное описание и рисунок к ней, надеюсь рисунок понятный. Находим минимальную точку по У,это у точка 2 (4;1). Провели перпендикуляр к оси оХ. Получили две плоскости. Слева остались точки: 6 (3;7), 4 (3;3), 1 (1;2).Самой левой к точке 2 будет точка 1(наверно точнее так,у прямой 12 образуется больший угол с перпендикуляром).Мы нашли первую точку - это 1. Теперь все повторям для точки 1. Проводим перпендикуляр к оси оУ(если развернуть рисунок на 90 градусов, то к оси оХ). Получили также две плоскости. Слева(сверху) остались точки 4,5,3,6,7. Больший угол к перпендикуляру составляет прямая 16. Мы нашли следующую точку - 6. и так далее.
l_inc А кто-то выше ратовал за то что учебная задача это совсем не то же самое что техническая )) Проверяющая программа это надо полагать система автоматической проверки результатов на олимпиаде? Так демонстрашка предназначена для ТС, а не для неё Спасибо - не сообразил редко консолю
Y_Mur Из того, как звучал вопрос, и что они мне ответили, мне показалось что символы '1' и '0' надо рассматривать как '1' - 0011 0001 '0' - 0011 0000. Тогда я не пойму, как получить ответ. =-0. Я не знаю что делать
REASY Насколько я понимаю #39 означает что ты изначально (в #1) верно понял замысел авторов задачи не связываться с битовыми масками, а делать вид что символы "0", "1" якобы и есть биты собранные в строку из якобы бит, которые на самом деле 8-битовые символы, но ты об этом даже и не подозреваешь, до тех пор пока тебя всякие Y_Mur-ы с единственно верного пути не собьют )) А что такое "ответ. =-0"? - моя твоя не понимает
REASY Действительно попробуй может l_inc прав: Хотя имхо медитировать над кодом нужно для души и дзена, и не расстраиваться по поводу искусствено придуманных "олимпийский" рекордов с бредовато сформулированными условиями
REASY Хм, идея хорошая. Только как определить, когда именно "переворачивать" разбивающий перпендикуляр на pi/2? Например, если у нас там, скажем, получается правильный 100-угольник?
DEEP В графическом решении мы опускаем перпендикуляр сначала на ось оХ,затем на ось оУ,и так через один.
Тем не менее, это будет правильно работать лишь в (условно) III четверти многоугольника. Ведь как замерить угол? Нужно опять же взять два вектора. Первый - это перпендикуляр. Начинается в "тестовой" точке, кончается где-то в +INF. Второй - соответственно проверяемый. Начинается в той же самой точке, кончается в некоторой другой. Если же "тестовая" точка находится не в третьей четверти (при условном делении контура на четверти, подобно координатной плоскости) - результаты непредсказуемы. Рисунок пояснит мою мысль.
REASY Неверное у Вас решение. Сама идея работы с перпендикулярами к двум осям даёт правильные решения только в частных случаях. Честно говоря, даже лень объяснять, почему.
REASY В аттаче. После нахождения точки (2) слева от возможных перпендикуляров не окажется ни одной точки. Если еще немного додумаете и откажетесь от перпендикуляров, то придёте к способу из поста 40.
