Задачка о трёх векторах(оптимизация на размер)

Тема в разделе "WASM.A&O", создана пользователем Black_mirror, 19 окт 2009.

  1. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    В регистрах AX,BX и CX находятся три различных(никакая пара из них не лежит на одной прямой) ненулевых вектора. В младшем байте находится компонента X, а в старшем - Y (целые 8-разрядные числа со знаком в диапазоне от -128 до 127). Необходимо записать в регистр AL число 1, если при повороте вектора A по часовой стрелке сначала он совпадёт с вектором B, а при дальнейшем повороте с вектором С, и 0 в противном случае.
    Например, если AX=0001h, BX=0100h, CX=00FFh, то нужно в AL записать 1.
    А если AX=7F80h, BX=0100h, CX=8000h, то 0.
     
  2. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    В примерах баг, должно быть:
    если AX=0001h, BX=0100h, CX=00FFh, то нужно в AL записать 0.
    А если AX=7F80h, BX=0100h, CX=8000h, то 1.

    Еще несколько примеров:

    AX=1122h, BX=3344, CX=5566 => AL=0.
    AX=7F7Fh, BX=8080, CX=FF00 => AL=0.
    AX=7F00h, BX=FF01, CX=FFFF => AL=1.
     
  3. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Может преобразовать вектор в угол, по таблице? И далее вычтя первый угол из второго и третьего, сравнить? Правда таблица будет неслабого размера, но быстро будет ^) Хотя таблицу наверняка можно уменьшить.
     
  4. n0name

    n0name New Member

    Публикаций:
    0
    Регистрация:
    5 июн 2004
    Сообщения:
    4.336
    Адрес:
    Russia
    16 Кб - много? :)
     
  5. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    Booster
    n0name
    Практического применения у этой задачки нет, так что про таблицы забудьте. Вообще есть решение которое основывается только на скалярных произведениях векторов. Без всяких делений и тригонометрических функций. Но может есть и другие варианты. А про таблицы может будет следующая задачка)
     
  6. n0name

    n0name New Member

    Публикаций:
    0
    Регистрация:
    5 июн 2004
    Сообщения:
    4.336
    Адрес:
    Russia
    смотрим знаки векторных произведений? не?
     
  7. t00x

    t00x New Member

    Публикаций:
    0
    Регистрация:
    15 фев 2007
    Сообщения:
    1.921
    Black_mirror
    AX=1100; BX=0302; CX=0604; => ?
     
  8. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    t00x
    Тут B и C на одной прямой лежат, по условию задачи таких данных быть не может. В таких случаях можно вернуть 0, или 1, или вообще любое значение.
     
  9. t00x

    t00x New Member

    Публикаций:
    0
    Регистрация:
    15 фев 2007
    Сообщения:
    1.921
    Black_mirror
    пардон, перечитал условие :)

    0. Делим плоскость на четверти и устанавливаем правила:
    Четверть (Y,X)
    1четверть (+,+)
    2четверть (+,-)
    3четверть (-,-)
    4четверть (-,+)
    Правило 0. 1ч < 2ч < 3ч < 4ч < 1ч - наивысший приоритет.
    Если AXч > BXч > CXч => 1
     
  10. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    t00x
    А можно на примере как это работает?
     
  11. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    Нашел еще один глюк в условии.
    Вектора на одной прямой лежать могут(не больше двух), но только если они направлены в противоположные стороны.
     
  12. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    http://ru.wikipedia.org/wiki/Псевдоскалярное_произведение

    BX /\ AX <= 0
    BX /\ CX >= 0
     
  13. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
  14. t00x

    t00x New Member

    Публикаций:
    0
    Регистрация:
    15 фев 2007
    Сообщения:
    1.921
    Black_mirror
    для векторов, лежащих в разных четвертях (24 случая из 64)
    Код (Text):
    1.   and AX, 0x8080
    2.   shr AX, 2
    3.   and BX, 0x8080
    4.   shr BX, 3
    5.   and CX, 0x8080
    6.   shr CX, 4
    7.   or AX, BX
    8.   or AX, CX
    9.   AX in [0A, 0B, 0C, 0D, 11, 13, 14, 16, 19, 1A, 1D, 1E, 21, 22, 25, 26, 29, 2B, 2C, 2E, 32, 33, 34, 35] ;1-ая таблица (64 бита) - вектора в разных четвертях
    10.   jnc @exit
    11.   AX in [0C, 0D, 11, 13, 1A, 1E, 22, 26, 29, 2E, 34, 35] ;2-ая таблица (64 бита) - единицы если выполняется условие
    12. @exit:
    примерно так, если не смущает оператор in
     
  15. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    qqwe
    Псевдоскалярное произведение здесь может быть и полезно, только вот мне не совсем ясно, какой будет результат в AL, если к примеру
    BX /\ AX > 0
    BX /\ CX >= 0
    ?

    t00x
    А что в остальных 40 случаях делать будем?)
     
  16. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Знаки трёх векторных произведений дают однозначную картину.
     
  17. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    Black_mirror
    гдето так. Booster прав, надо знаки 3рех произведений
    Код (Text):
    1. ;al = Ax
    2. ;ah = Ay
    3.  
    4. ;bl = Bx
    5. ;bh = By
    6.  
    7. ;cl = Cx
    8. ;ch = Cy
    9.  
    10. ;ebx = ?
    11.  
    12.  
    13. main:
    14.   xchg ax,bx
    15.   mov di,ax
    16.  B_A:
    17.   call det    ; B/\A
    18.   xchg ax,di
    19.  B_C:
    20.   xchg bx,cx
    21.   call det    ; B/\C
    22.   xor di,ax
    23.  A_C:
    24.   xchg ax,cx
    25.   call det    ; A/\C
    26.   xor ax,di
    27.   shr ax,15
    28.        ; ax = 1 если A --> B --> C. иначе 0
    29.  
    30. .................
    31.  
    32. det: ; A/\B.  A = (al, ah), B = (bl, bh).
    33.   mov dx,ax
    34.   xchg al,ah
    35.   imul bl
    36.   xchg dx,ax
    37.   imul bh
    38.   sub ax,dx
    39.   ret
    есть оно но. если все 3 окажутся на одной линии, то результат будет 0 в любом случае, в независимости от направлений векторов
     
  18. n0name

    n0name New Member

    Публикаций:
    0
    Регистрация:
    5 июн 2004
    Сообщения:
    4.336
    Адрес:
    Russia
    угу, я об этом писал в 6 посте.
     
  19. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.035
    n0name
    qqwe
    Booster

    Вот пара примеров:
    A=(2,1) B=(0,1) C=(-2,1)
    B/\A=-2 B/\C=2 A/\C=4

    A=(2,-1) B=(0,1) C=(-2,-1)
    B/\A=-2 B/\C=2 A/\C=-4
    Как видите здесь знак третьего произведения поменялся, но в обоих примерах вектор A лежит справа от B, а вектор C
    слева. И какую операцию будете делать со знаками чтобы получить результат?!
     
  20. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    A зачем так в разнобой? A^B=+; B^C=+; В принципе дальше можно не считать. Вот если бы B^C=-; тогда нужно смотреть A^C;