Помогите с олимпиадой

Тема в разделе "WASM.BEGINNERS", создана пользователем REASY, 15 сен 2008.

  1. DEEP

    DEEP Андрей

    Публикаций:
    0
    Регистрация:
    27 апр 2008
    Сообщения:
    491
    Адрес:
    г. Владимир
    REASY
    Думаю, вариант с "нижней + левой" точками неверен. Вот пример: Мы включили в Контур точки 1 и 2 - это верно. Далее, мы ведь ищем следующую "самую нижнюю" точку после [2], верно? Это у нас [1]. Левее неё нет ничего. Берём следующую "нижнюю". Тут их аж три. Пойдём по возрастанию - пусть первой будет [3]. И какая же для неё самая левая? Несомненно, [6]. В итоге мы забываем про [7].
     
  2. DEEP

    DEEP Андрей

    Публикаций:
    0
    Регистрация:
    27 апр 2008
    Сообщения:
    491
    Адрес:
    г. Владимир
    А алгоритм мой для определения полуплоскости, в которой лежит точка относительно вектора, вычисляет не что иное как скалярное произведение двух векторов:
    Первый из них - с началом в точке 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.

    ЗЫ.
    Чёрт. Во блин что значит температура. Право и лево перепутал =(
    Всё, уже поправил.
    Однако если вы это читали до времени последнего редактирования, знайте: где было право - стало лево %)
    Ещё раз простите. Надо было сразу жаропонижающее пить...
     
  3. Y_Mur

    Y_Mur Active Member

    Публикаций:
    0
    Регистрация:
    6 сен 2006
    Сообщения:
    2.494
    REASY
    тогда в твоём первоначальном коде можно придраться разве только к отсутствию проверок на недопустимость символов и оптимизации программы, но вроде ни то ни другое не требовалось.

    Если всё-же захочешь разобраться с битовым вариантом, то вот:
    правда из-за кривизны консоли текстовка на английском (SetConsoleOutputCP не помогла, а с CharToOem связываться неохота), но комменты имхо достаточно подробные.

    Код (Text):
    1. // Имитация передачи и приёма с сэмплированием для устранения помех
    2. #include "stdafx.h"
    3. #include <iostream>
    4. #include <string>
    5. #include <stdlib.h>
    6. using namespace std;
    7.  
    8. int main(int argc, char **argv)
    9. {
    10.     string str_kb_in;   // Строка с передаваемыми данными введёнными с клавиатуры
    11.     int k;              // Коэффициент сэмплирования
    12.  
    13.     cout << "k = ";
    14.     cin >> k;
    15.     // Проверка k на чётность и исправление если не так
    16.     if (k % 2 == 0)
    17.     {
    18.         k++;
    19.         cout << "Not even k correct to k = " << k << '\n';
    20.     }
    21.  
    22.     // Ввод передаваемой строки (допустимы любые символы кроме пробела (дефект cin))
    23.     cout << "Input text for transmit: \n";
    24.     cin >> str_kb_in;
    25.  
    26.     int len_kb = str_kb_in.length();
    27.     int i, b, m;    // счётчики
    28.  
    29.     // Вывод битового представления текста (не очень красиво но для примера сойдёт ;)
    30.     // все биты по очереди сдвигаются в младший и "лишние" (все кроме младшего) обнуляются по маске
    31.     cout << "\nThe bin format of this text: \n";
    32.     for (i = 0; i < len_kb; i++)
    33.         for (b = 7; b >= 0; b--)
    34.             cout << ((str_kb_in[i] >> b) & 0x1);
    35.     cout << '\n';
    36.  
    37.     // Подготовка к передаче повтором битов k раз
    38.     string str_in_receiver = "";        // битовая строка подготовленная для передачи
    39.     int cb = 0; // счётчик бит в str_in_receiver
    40.     char currernt_char = 0 ; // текущий символ для str_in_receiver
    41.  
    42.     for (i = 0; i < len_kb; i++)    // счётчик символов в строке
    43.         for (b = 7; b >= 0; b--)    // счётчик бит в байте
    44.             for (m = 0; m < k; m++) // счётчик повторов (сэмплов)
    45.             {
    46.                 currernt_char = (currernt_char  << 1) | ((str_kb_in[i] >> b) & 0x1);
    47.                 if (++cb > 7)
    48.                 {
    49.                     cb = 0;
    50.                     str_in_receiver += currernt_char;
    51.                     currernt_char = 0;
    52.                 }
    53.             }
    54.             // коррекция "хвоста" (заполнение нулями)
    55.             if (cb != 0) str_in_receiver += currernt_char << (8 - cb);
    56.             // потом лишние нули игнорируется поскольку приёмник возьмёт только кратное k количество бит,
    57.             // но они нужны при хранении битовой строки в символьном массиве string
    58.     cout << '\n';
    59.  
    60.     // Вывод передаваемой битовой строки (не очень красиво но для примера сойдёт ;)
    61.     cout << "The transmit format of this text in bin format: \n";
    62.     int len_transmit = str_in_receiver.length();
    63.     for (i = 0; i < len_transmit; i++)
    64.         for (b = 7; b >= 0; b--)
    65.             cout << ((str_in_receiver[i] >> b) & 0x1), '\n';
    66.     cout << '\n';
    67.    
    68.     // Генерируем случайный шум и портим им данные
    69.     int level_noise;
    70.     // Запрос уровня шума на линии
    71.     cout << "===============================================\n";
    72.     cout << "Input level noise (1 - Lo, 2 - Medium, 3 - Hi):\n";
    73.     cin >> level_noise;
    74.     len_transmit = str_in_receiver.length();
    75.     for (i = 0; i < len_transmit; i++)
    76.     {  
    77.         switch(level_noise)
    78.         {
    79.         case 1: // слабый шум
    80.             // случайное добавление 1
    81.             str_in_receiver[i] |= ((rand() * 255 / RAND_MAX)&(rand() * 255 / RAND_MAX)&(rand() * 255 / RAND_MAX)&(rand() * 255 / RAND_MAX));
    82.             // случайное добавление 0
    83.             str_in_receiver[i] &= ((rand() * 255 / RAND_MAX)|(rand() * 255 / RAND_MAX)|(rand() * 255 / RAND_MAX)|(rand() * 255 / RAND_MAX));
    84.             break;
    85.         case 2: // средний шум - нужно больше повторов
    86.             // случайное добавление 1
    87.             str_in_receiver[i] |= ((rand() * 255 / RAND_MAX)&(rand() * 255 / RAND_MAX)&(rand() * 255 / RAND_MAX));
    88.             // случайное добавление 0
    89.             str_in_receiver[i] &= ((rand() * 255 / RAND_MAX)|(rand() * 255 / RAND_MAX)|(rand() * 255 / RAND_MAX));
    90.             break;
    91.         default:    // сильный шум - нужно много повторов
    92.             // случайное добавление 1
    93.             str_in_receiver[i] |= ((rand() * 255 / RAND_MAX)&(rand() * 255 / RAND_MAX));
    94.             // случайное добавление 0
    95.             str_in_receiver[i] &= ((rand() * 255 / RAND_MAX)|(rand() * 255 / RAND_MAX));
    96.         }
    97.     }
    98.  
    99.     // Вывод принятой битовой строки содержащей смесь шума и данных
    100.     cout << "\nThe received bin data & noise: \n";
    101.     len_transmit = str_in_receiver.length();
    102.     for (i = 0; i < len_transmit; i++)
    103.         for (b = 7; b >= 0; b--)
    104.             cout << ((str_in_receiver[i] >> b) & 0x1), '\n';
    105.     cout << '\n';
    106.  
    107.     // ====== наконец добрались до анализа принимаемых данных =======
    108.     // считаем что длина передаваемой строки нам известна (как правило в реальных задачах так оно и есть)
    109.     // Берём очередной символ в принятой строке
    110.     // начиная со старшего бита прогоняем блоки по k бит
    111.     // суммируем биты, проверяем сумму на больше чем k / 2 (целочисленно)
    112.     // добавляем в символы выходной строки биты от старшего к младшему
    113.     // если счётчик k прогонов перешагнул 8 бит переходим к следующему символу в строке str_in_receiver
    114.  
    115.     string str_result = "";
    116.     cb = 7;             // счётчик бит
    117.     int p = 0;          // указатель в строке str_in_receiver (уже с шумами)
    118.     currernt_char = 0;  // текущий символ
    119.     int bit_state = 0;  // состояние принимаемого бита (счётчик)
    120.  
    121.     for (i = 0; i < len_kb; i++)    // счётчик символов в строке str_result
    122.     {
    123.         for (b = 7;  b >= 0; b--)   // счётчик бит в байте для str_result
    124.         {
    125.             for (m = 0; m < k; m++) // счётчик повторов (сэмплов)
    126.             {   // считаем количество единиц в блоке из k бит
    127.                 bit_state += ((str_in_receiver[p] >> cb) & 0x1);
    128.                 if (--cb < 0)   // переход к следующему символу в str_in_receiver
    129.                 {
    130.                     ++p;
    131.                     cb = 7;
    132.                 }
    133.             }
    134.             // помещаем в младший бит 1 если bit_state > (k / 2) или 0 если bit_state < (k / 2)
    135.             // равенство исключается нечётностью k
    136.             if (bit_state > (k >> 1))   // здесь k >> 1 = k / 2 (целочисленно)
    137.                 currernt_char |= 1 << b;    // ноль помещать не обязательно он там и так есть :)
    138.                                             // а 1 "угоняем" в старшие биты насколько нужно
    139.             bit_state = 0;  // очищаем счётчик для следующих бит
    140.         }
    141.         str_result += currernt_char;
    142.         currernt_char = 0;
    143.     }
    144.     // хвост с нолями и помехами остаётся нерассмотренным за ненадобностью ;)
    145.    
    146.     cout << "\nThe result of transmit & received (bin format): \n";
    147.  
    148.     for (i = 0; i < len_kb; i++)
    149.         for (b = 7; b >= 0; b--)
    150.             cout << ((str_result[i] >> b) & 0x1);
    151.     cout << '\n';
    152.  
    153.     cout << "\nThe result of transmit & received (text format): \n";
    154.     cout << str_result << '\n';
    155.  
    156. //  cin >> currernt_char; // чтобы не закрывалась сразу в релиз версии
    157.  
    158.     return 0;
    159. }
    Релиз на всякий случай прицепил.
     
  4. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    Y_Mur
    Низзя в таких задачах ничего лишнего на консоль выдавать. :) При первом же милом приглашении вида
    программа проверки пошлет кодера вместе с его программой на все три.
    Если исходник набирать в кодировке DOS (например выставить шрифт Terminal в настройках IDE), то на консоль выводится в том же виде, что и в исходнике.
    Ну я бы вообще отказался от всей этой ООП-шной бредятины вида +='0'. Использовал бы printf/scanf вместо cout/cin. А буфер для строки выделил бы заранее. Т.е. в виде char inputStr[10001]. Возможно на проверяющей стороне проблемы с выделением/перевыделением/передовыделением памяти в рантайме (подозрение, что пятый тест - тест на 10000 символов в строке). Разумеется, не факт, что поможет, но ИМХО попробовать очень даже стоит.
     
  5. REASY

    REASY New Member

    Публикаций:
    0
    Регистрация:
    24 дек 2007
    Сообщения:
    108
    File 1.txt:
    ```
    #/usr/bin/perl
    print "9999\n";
    print "100"x3333;
    ```
    perl 1.txt | "4.Передача информации.exe"
    9999
    0
    Вроде быстро считает
     
  6. REASY

    REASY New Member

    Публикаций:
    0
    Регистрация:
    24 дек 2007
    Сообщения:
    108
    Y_Mur
    Спасибо большое, очень интересный пример.
    Теперь лучше понимается, что по проводам не символы '1','0' передаются, а биты ^^
     
  7. REASY

    REASY New Member

    Публикаций:
    0
    Регистрация:
    24 дек 2007
    Сообщения:
    108
    Насчет этого
    Вот более подробное описание и рисунок к ней, надеюсь рисунок понятный.
    Находим минимальную точку по У,это у точка 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. и так далее.
     
  8. Y_Mur

    Y_Mur Active Member

    Публикаций:
    0
    Регистрация:
    6 сен 2006
    Сообщения:
    2.494
    l_inc
    А кто-то выше ратовал за то что учебная задача это совсем не то же самое что техническая ;)))
    Проверяющая программа это надо полагать система автоматической проверки результатов на олимпиаде?
    Так демонстрашка предназначена для ТС, а не для неё ;)

    Спасибо - не сообразил редко консолю ;)
     
  9. REASY

    REASY New Member

    Публикаций:
    0
    Регистрация:
    24 дек 2007
    Сообщения:
    108
    Y_Mur
    Из того, как звучал вопрос, и что они мне ответили, мне показалось что символы '1' и '0' надо рассматривать как
    '1' - 0011 0001
    '0' - 0011 0000.
    Тогда я не пойму, как получить ответ. =-0. Я не знаю что делать
     
  10. Y_Mur

    Y_Mur Active Member

    Публикаций:
    0
    Регистрация:
    6 сен 2006
    Сообщения:
    2.494
    REASY
    Насколько я понимаю #39 означает что ты изначально (в #1) верно понял замысел авторов задачи не связываться с битовыми масками, а делать вид что символы "0", "1" якобы и есть биты собранные в строку из якобы бит, которые на самом деле 8-битовые символы, но ты об этом даже и не подозреваешь, до тех пор пока тебя всякие Y_Mur-ы с единственно верного пути не собьют :)))

    А что такое "ответ. =-0"? - моя твоя не понимает ;)
     
  11. REASY

    REASY New Member

    Публикаций:
    0
    Регистрация:
    24 дек 2007
    Сообщения:
    108
    Y_Mur
    Более точно:
    "Тогда я не пойму, как получить ответ!!????!?!. =-0 - безысходность)).
     
  12. Y_Mur

    Y_Mur Active Member

    Публикаций:
    0
    Регистрация:
    6 сен 2006
    Сообщения:
    2.494
    REASY
    Действительно попробуй может l_inc прав:
    Хотя имхо медитировать над кодом нужно для души и дзена, и не расстраиваться по поводу искусствено придуманных "олимпийский" рекордов с бредовато сформулированными условиями ;)
     
  13. REASY

    REASY New Member

    Публикаций:
    0
    Регистрация:
    24 дек 2007
    Сообщения:
    108
    Y_Mur
    Буду стараться, спасибо!
     
  14. DEEP

    DEEP Андрей

    Публикаций:
    0
    Регистрация:
    27 апр 2008
    Сообщения:
    491
    Адрес:
    г. Владимир
    REASY
    Хм, идея хорошая.
    Только как определить, когда именно "переворачивать" разбивающий перпендикуляр на pi/2?
    Например, если у нас там, скажем, получается правильный 100-угольник?
     
  15. REASY

    REASY New Member

    Публикаций:
    0
    Регистрация:
    24 дек 2007
    Сообщения:
    108
    DEEP
    В графическом решении мы опускаем перпендикуляр сначала на ось оХ,затем на ось оУ,и так через один.
     
  16. DEEP

    DEEP Андрей

    Публикаций:
    0
    Регистрация:
    27 апр 2008
    Сообщения:
    491
    Адрес:
    г. Владимир
    Тем не менее, это будет правильно работать лишь в (условно) III четверти многоугольника. Ведь как замерить угол? Нужно опять же взять два вектора. Первый - это перпендикуляр. Начинается в "тестовой" точке, кончается где-то в +INF. Второй - соответственно проверяемый. Начинается в той же самой точке, кончается в некоторой другой. Если же "тестовая" точка находится не в третьей четверти (при условном делении контура на четверти, подобно координатной плоскости) - результаты непредсказуемы. Рисунок пояснит мою мысль.
     
  17. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    REASY
    Неверное у Вас решение. Сама идея работы с перпендикулярами к двум осям даёт правильные решения только в частных случаях. Честно говоря, даже лень объяснять, почему.
     
  18. REASY

    REASY New Member

    Публикаций:
    0
    Регистрация:
    24 дек 2007
    Сообщения:
    108
    l_inc
    Не надо объяснять, лучше дайте пример точек
     
  19. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    REASY
    В аттаче. После нахождения точки (2) слева от возможных перпендикуляров не окажется ни одной точки. Если еще немного додумаете и откажетесь от перпендикуляров, то придёте к способу из поста 40.
     
  20. DEEP

    DEEP Андрей

    Публикаций:
    0
    Регистрация:
    27 апр 2008
    Сообщения:
    491
    Адрес:
    г. Владимир
    =del=