Współliniowość trzech punktów

Wejście: trzy punkty a, b i c
Wyjście: określić po której stronie prostej ab leży punkt c.
Złożoność: O(1)

Określenie strony, po której leży jest równoznaczne z określeniem kąta zawartego pomiędzy wektorem ab i ac. Jeżeli kąt ten jest z zakresu (0, pi) to punkt leży po lewej stronie. Jeżeli (pi, 2pi) to po prawej. Jeżeli kąt jest równy 0 to punkt leży na prostej - punkty a, b i c są współliniowe.
//TODO: umieścić rysunki.

Aby wyznaczyć kąt pomiędzy wektorami należy obliczyć wyznacznik macierzy det(a, b, c):
|a0 a1 1|
|b0 b1 1|=sin kąta pomiędzy ab i ac
|c0 c1 1|

Wyznacznik mniejszy od 0 oznacza, że punkt leży po lewej stronie. Większy, że leży po prawej.

class vector(tuple):
    def __add__(self, other):
	''' Dodawanie wektorow. '''
	return vector([i+j for i, j in zip(self, other)])
    def __mul__(self, other):
	''' Mnozenie przez stala. '''
	return vector([i*other for i in self])
    def __sub__(self, other):
	''' Odejmowanie wektorow. '''
	return vector([i-j for i, j in zip(self, other)])
    def dot(self, other):
	''' Iloczyn skalarny wektorow. '''
	return sum((i*j for i, j in zip(self, other)))

def det(a, b, c):
    ''' Wyznacznik macierzy. '''
    a0, a1 = a
    b0, b1 = b
    c0, c1 = c
    return a0*b1+a1*c0+b0*c1-a0*c1-a1*b0-c0*b1

a = vector((a0, a1))
b = vector((b0, b1))
c = vector((c0, c1))
result = det(a, b, c)
if result < 0:
    print 'punkt lezy po lewej stronie prostej'
elif result > 0:
    print 'punkt lezy po prawej stronie prostej'
else:
    print 'punkt lezy na prostej'