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

В регистрах 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.

 

В примерах баг, должно быть:
если 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.

 

Может преобразовать вектор в угол, по таблице? И далее вычтя первый угол из второго и третьего, сравнить? Правда таблица будет неслабого размера, но быстро будет ^) Хотя таблицу наверняка можно уменьшить.

 

16 Кб - много?

 

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

 

смотрим знаки векторных произведений? не?

 

Black_mirror
AX=1100; BX=0302; CX=0604; => ?

 

t00x
Тут B и C на одной прямой лежат, по условию задачи таких данных быть не может. В таких случаях можно вернуть 0, или 1, или вообще любое значение.

 

Black_mirror
пардон, перечитал условие

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

 

t00x
А можно на примере как это работает?

 

Нашел еще один глюк в условии.
Вектора на одной прямой лежать могут(не больше двух), но только если они направлены в противоположные стороны.

 

http://ru.wikipedia.org/wiki/Псевдоскалярное_произведение

BX /\ AX <= 0
BX /\ CX >= 0

 

?

 

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

 

qqwe
Псевдоскалярное произведение здесь может быть и полезно, только вот мне не совсем ясно, какой будет результат в AL, если к примеру
BX /\ AX > 0
BX /\ CX >= 0
?

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

 

Знаки трёх векторных произведений дают однозначную картину.

 

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 в любом случае, в независимости от направлений векторов

 

угу, я об этом писал в 6 посте.

 

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
слева. И какую операцию будете делать со знаками чтобы получить результат?!

 

A зачем так в разнобой? A^B=+; B^C=+; В принципе дальше можно не считать. Вот если бы B^C=-; тогда нужно смотреть A^C;