Pripadnost tačke trouglu

Napiši program koji proverava da li se tačka nalazi u unutrašnjosti trougla.

Opis ulaza

Sa standardnog ulaza se unosi 8 realnih brojeva iz intervala \([-10, 10]\), zaokruženih na dve decimale. U prvom redu se unose \(x\) i \(y\) koordinata tačke koja se analizira, a u naredna tri reda \(x\) i \(y\) koordinate temena trougla. Među 4 unete tačke nema kolinearnih.

Opis izlaza

Na standardni izlaz ispisati da ako tačka pripada trouglu ili ne ako ne pripada.

Primer

Ulaz

0.00 2.00
-3.00 -3.00
-1.00 4.00
3.00 2.00

Izlaz

da

Rešenje

Opis glavnog rešenja

Tačka \(S\) je unutar trougla \(ABC\) ako i samo ako je tačka \(S\) sa iste strane prave \(AB\) kao i tačka \(C\), sa iste strane prave \(BC\) kao i tačka \(A\) i sa iste strane tačke \(AC\) kao i tačka \(B\) tj. ako svi trouglovi \(ABS\), \(BCS\) i \(CAS\) imaju istu orijentaciju.

#include <iostream>
#include <vector>

using namespace std;

struct Point {
    double x;
    double y;
};

double orientation(const Point &A, const Point &B, const Point &C) 
{
    return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}

bool in_triangle(const Point &A, const Point &B, const Point &C, 
                 const Point &S)
{
    double o1 = orientation(A, B, S);
    double o2 = orientation(B, C, S);
    double o3 = orientation(C, A, S);

    if ((o1 > 0 && o2 > 0 && o3 > 0) ||
        (o1 < 0 && o2 < 0 && o3 < 0)) {
        return true;
    }

    return false;
}

int main(void)
{
    Point S, A, B, C;

    cin >> S.x >> S.y;
    cin >> A.x >> A.y;
    cin >> B.x >> B.y;
    cin >> C.x >> C.y;

    if (in_triangle(A, B, C, S)) {
        cout << "da" << endl;
    } else {
        cout << "ne" << endl;
    }

    return 0;
}