# racunanje vektorskog proizvoda vektora a=(a1, a2, ..., an) i b=(b1, b2, ..., bn)
def skalarniProizvod(vect_a, vect_b):
 
    p = 0
    n=len(vect_a)

    for i in range(0, n):
        p = p + vect_a[i] * vect_b[i]
 
    return p


# provera normalnosti vektora a=(x1, y1, z1) i b=(x2, y2, z2)
def proveraNormalnosti(x1, y1, z1, x2, y2, z2):
     
    a = [x1, y1, z1]
    b = [x2, y2, z2]
 
    
    skalarni=skalarniProizvod(a, b)
 
    # provera da li je izracunati vektorski proizvod nula vektor ili ne
    if (skalarni == 0):
        print("Vektori su medjusobno normalni.")
    else:
        print("Vektori nisu medjusobno normalni.")


# racunanje vektorskog proizvoda vektora a=(x1, y1, z1) i b=(x2, y2, z2)
def vektorskiProizvod(vect_a, vect_b):

    vektorski_P = [0,0,0]
    
    vektorski_P[0] = (vect_a[1] * vect_b[2] - vect_a[2] * vect_b[1])
 
    vektorski_P[1] = (vect_a[2] * vect_b[0] - vect_a[0] * vect_b[2])
 
    vektorski_P[2] = (vect_a[0] * vect_b[1] - vect_a[1] * vect_b[0])

    return vektorski_P


# provera kolinearnosti vektora  a=(x1, y1, z1) i b=(x2, y2, z2)
def kolinearnostVektora(x1, y1, z1, x2, y2, z2):
     
    a = [x1, y1, z1]
    b = [x2, y2, z2]
 
    # racunanje vektorskog proizvoda
    vektorski_P = vektorskiProizvod(a, b)
 
    # provera da li je izracunati vektorski proizvod nula vektor ili ne
    if (vektorski_P[0] == 0 and
        vektorski_P[1] == 0 and
        vektorski_P[2] == 0):
        return True
    else:
        return False


# provera kolinearnosti tacaka A=(x1, y1), B=(x2, y2) i C=(x3,y3)
def kolinearnostTacaka(x1, y1, x2, y2, x3, y3):
     
    a = [x2-x1, y2-y1, 0]
    b = [x3-x1, y3-y1, 0]

    return kolinearnostVektora(a, b)


# provera da li se dve duzi AB i CD seku
# klasa tacka
class Tacka:
    def __init__(self, x, y):
        self.x = x
        self.y = y

# provera da li tacka Q pripada duzi PR
def naDuzi(P, Q, R):
    if ( (Q.x <= max(P.x, R.x)) and (Q.x >= min(P.x, R.x)) and
           (Q.y <= max(P.y, R.y)) and (Q.y >= min(P.y, R.y))):
        return True
    return False

def orijentacija(A, B, C):
    # trazimo orijentaciju ACxAB
    # funkcija vraca sledece vrednosti:
    # 0 : kolinearne tacke
    # 1 : u smeru kazaljki na satu (negativan smer)
    # 2 : u smeru kontra od smera kretanja kazaljki na satu (pozitivan smer)
     
    
    val = (float(B.y - A.y) * (C.x - A.x)) - (float(B.x - A.x) * (C.y - A.y))
    if (val > 0):
         
        # negativan smer
        return 1
    elif (val < 0):
         
        # pozitivan smer
        return 2
    else:
           
        # kolinearne tacke
        return 0

def Presek(A, B, C, D):
     
    o1 = orijentacija(A, B, C)
    o2 = orijentacija(A, B, D)
 
    # orijentacije su razlicite ili je neka 0, tada se duzi seku
    if ((o1 != o2) or (o1 == 0) or (o2 == 0)):
        return True

    return False

# funkcija se moze proveriti npr. pozivima
# Presek(Tacka(1,1), Tacka(10,1), Tacka(0,5), Tacka(2,5)), rezultat je False
# Presek(Tacka(-5,-5), Tacka(0,0), Tacka(1,1), Tacka(10,10)), resultat je True



#provera da li se tacka P(x,y) nalazi u trouglu zadatom temenima A(x1,y1), B(x2,y2), C(x3,y3)
def povrsinaTrougla(x1,y1,x2,y2,x3,y3):
    
    return abs((x1*(y2-y3)+(x2*(y3-y1))+(x3*(y1-y2)))/2.0)


def uTrouglu(x1, y1, x2, y2, x3, y3, x, y):
 
    # povrsina trougla ABC
    A = povrsinaTrougla(x1, y1, x2, y2, x3, y3)
 
    # povrsina trougla PBC
    A1 = povrsinaTrougla(x, y, x2, y2, x3, y3)
     
    # povrsina trougla PAC
    A2 = povrsinaTrougla(x1, y1, x, y, x3, y3)
     
    # povrsina trougla PAB
    A3 = povrsinaTrougla(x1, y1, x2, y2, x, y)
     
    if(A == A1 + A2 + A3):
        return True
    else:
        return False


# izracunavanje povrsine konveksnog poligona zadatog temenima
# (X[i], Y[i]) su koordinate i-tog temena
def povrsinaPoligona(X, Y, n):
  
    # inicijalna povrsina
    povrsina = 0.0
  
    j = n - 1
    for i in range(0,n):
        povrsina += (X[j] + X[i]) * (Y[j] - Y[i])
        j = i
      
  
    return int(abs(povrsina / 2.0))