Proiect AF - Triangularea unui poligon

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;

#define x first
#define y second

#define for_nrVarfuri for (int i = 0; i < nrVf; i++)
#define for_(x) for(auto& it : x)

typedef pair<float, float> Punct;
typedef pair<Punct, Punct> Segment;

void citire(int& nrVf, vector<Punct>& vf)
{
    ifstream fin("triangulare.in");

    fin >> nrVf;
    vf.resize(nrVf);

    for_(vf)
        fin >> it.x >> it.y;

    fin.close();
}

float Det(const Punct& p1, const Punct& p2, const Punct& p3)
{
    return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}

bool EsteInPoligon(int nrVf, vector<Punct> vf, const Punct& p)
{
    Punct q(1000000, rand() % 1000000);

    bool este = false;
    for_nrVarfuri
    {
        int j = (i + 1) % nrVf;

        if (Det(p, vf[i], vf[j]) * Det(q, vf[i], vf[j]) > 0 && Det(vf[i], p, q) * Det(vf[j], p, q) < 0)
            este ^= true;
    }

    return este;
}

bool IntersectieIntervale(double st1, double dr1, double st2, double dr2)
{
    if (st1 > st2)
    {
        swap(st1, st2);
        swap(dr1, dr2);
    }

    return dr1 - st2 > 0;
}

bool IntersectieSegmente(const Segment& s1, const Segment& s2)
{
    if (!Det(s1.x, s1.y, s2.x) && !Det(s1.x, s1.y, s2.y))
    {
        if (IntersectieIntervale(min(s1.x.x, s1.y.x), max(s1.x.x, s1.y.x), min(s2.x.x, s2.y.x), max(s2.x.x, s2.y.x))
            || IntersectieIntervale(min(s1.x.y, s1.y.y), max(s1.x.y, s1.y.y), min(s2.x.y, s2.y.y), max(s2.x.y, s2.y.y)))
            return true;
        else
            return false;
    }

    return (Det(s1.x, s1.y, s2.x) * Det(s1.x, s1.y, s2.y) < 0 && Det(s2.x, s2.y, s1.x) * Det(s2.x, s2.y, s1.y) < 0);
}

bool VerificareSegment(int nrVf, vector<Punct> vf, vector<Punct> tr, Segment segmCurent)
{
    for_nrVarfuri
        if (IntersectieSegmente(segmCurent, Segment(vf[i], vf[(i + 1) % nrVf])))
            return false;

    for_(tr)
        if (IntersectieSegmente(segmCurent, Segment(vf[it.x], vf[it.y])))
            return false;

    Punct q((segmCurent.x.x + segmCurent.y.x) / 2, (segmCurent.x.y + segmCurent.y.y) / 2);
    return EsteInPoligon(nrVf, vf, q);
}

void parcurgere(int nrVf, vector<Punct> vf, vector<Punct>& tr)
{
    for_nrVarfuri
        for (int j = (i + 2) % nrVf; (j + 1) % nrVf != i; j = (j + 1) % nrVf)
            if (VerificareSegment(nrVf, vf, tr, Segment(vf[i], vf[j])))
                tr.push_back({ min(i, j), max(i, j) });
}

void afisare(int nrVf, vector<Punct> vf, vector<Punct> tr)
{
    ofstream fout("triangulare.out");

    int contor = 1;
    for_(vf)
        fout << "Punctul " << setw(2) << contor++ << " are coordonatele (" << setw(3) << it.x << ", " << setw(3) << it.y << ") \n";

    if (nrVf < 3)
        fout << "Punctele introduse nu pot forma un poligon. Introduceti o valoare strict mai mare decat 3. \n";
    else
        if (nrVf == 3)
        {
            if (Det(vf[0], vf[1], vf[2]))
                fout << "Punctele introduse formeaza un triunghi. \n";
            else
                fout << "Punctele introduse nu formeaza un triunghi. \n";
        }
        else
        {
            contor = 1;
            fout << "\nIndicii varfurilor care formeaza segmentul respectiv: \n";
            for_(tr)
                fout << "Segmentul " << setw(2) << contor++ << " are capetele in varfurile cu indicii " << setw(2) << it.x + 1 << ' ' << setw(2) << it.y + 1 << " \n";
        }
}

int main()
{
    srand(time(NULL));
    int nrVarfuri;
    vector<Punct> vf, triangulare;

    citire(nrVarfuri, vf);
    parcurgere(nrVarfuri, vf, triangulare);
    sort(triangulare.begin(), triangulare.end());
    afisare(nrVarfuri, vf, triangulare);

    return 0;
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;

ifstream fin("triangulare.in");
ofstream fout("triangulare.out");

const double Zero = 1.0e-7; //10^(-7)

typedef pair<double, double> Punct; // struct Punct { double first, double second };
typedef pair<Punct, Punct> Segment; // struct Segment { Punct first, Punct second };

int nrVarfuri;
vector<Punct> poligon, triangulare;

bool EsteZero(const double& x)
{
    //Din cauza tipului double este posibil sa nu obtinem 0, ci rezultate apropiate de zero (de exemplu: 0.000012).
    //Vom face aproximarea lui Zero cu 10^(-7).

    return fabs(x) < Zero;
}

double Determinant(const Punct& p1, const Punct& p2, const Punct& p3)
{
    /*
        Determinantul se poate calcula dupa formula
        | xA yA 1 |
        | xB yB 1 |
        | xC yC 1 |

        in cazul nostru:

        | p1.first  p1.second   1 |
        | p2.first  p2.second   1 |
        | p3.first  p3.second   1 |.

        Putem calcula acest determinat punand conditia ca punctul C sa se situeze pe ecuatia dreptei determinata de punctele A, B:
        yC - yA     xC - xA
        -------- = ---------, relatie echivalenta cu (yC - yA)*(xB - xA) = (xC - xA)*(yB - yA), trecem ce se afla in membrul drept in membrul stang cu semn
        yB - yA     xB - xA                                                                     schimbat si obtinem relatia pe care o returnam.

        Datorita relatiei de mai sus verificam daca punctul C se afla pe ecuatia dreptei AB.


        Altfel spus, daca relatia de mai jos este 0 (cea pe care o returnam), atunci punctele sunt coliniare, altfel nu sunt coliniare.
    */

    return (p2.first - p1.first) * (p3.second - p1.second) - (p2.second - p1.second) * (p3.first - p1.first);

}

bool EsteInPoligon(const Punct& p)
{
    Punct q(1000000, rand() % 1000000);

    bool esteInPoligon = false;
    for (int i = 0; i < nrVarfuri; i++)
    {
        int j = (i + 1) % nrVarfuri;

        if (Determinant(p, poligon[i], poligon[j]) * Determinant(q, poligon[i], poligon[j]) > 0
            && Determinant(poligon[i], p, q) * Determinant(poligon[j], p, q) < -Zero)
            esteInPoligon ^= true;
    }

    return esteInPoligon;
}

bool IntersectieIntervale(double stanga1, double dreapta1, double stanga2, double dreapta2)
{
    if (stanga1 > stanga2)
    {
        swap(stanga1, stanga2);
        swap(dreapta1, dreapta2);
    }

    return dreapta1 - stanga2 > Zero;
}


bool IntersectieSegmente(const Segment& s1, const Segment& s2)
{
    if (EsteZero(Determinant(s1.first, s1.second, s2.first)) && EsteZero(Determinant(s1.first, s1.second, s2.second)))
    {
        if (IntersectieIntervale(min(s1.first.first, s1.second.first), max(s1.first.first, s1.second.first),
            min(s2.first.first, s2.second.first), max(s2.first.first, s2.second.first))
            || IntersectieIntervale(min(s1.first.second, s1.second.second), max(s1.first.second, s1.second.second),
                min(s2.first.second, s2.second.second), max(s2.first.second, s2.second.second)))
            return true;
        else
            return false;
    }

    return (Determinant(s1.first, s1.second, s2.first) * Determinant(s1.first, s1.second, s2.second) < -Zero
        && Determinant(s2.first, s2.second, s1.first) * Determinant(s2.first, s2.second, s1.second) < -Zero);
}

bool VerificareSegment(Segment cutSegment)
{
    for (int i = 0; i < nrVarfuri; i++)
    {
        if (IntersectieSegmente(cutSegment, Segment(poligon[i], poligon[(i + 1) % nrVarfuri])))
            return false;
    }

    for (auto& it : triangulare)
    {
        if (IntersectieSegmente(cutSegment, Segment(poligon[it.first], poligon[it.second])))
            return false;
    }

    return EsteInPoligon(Punct((cutSegment.first.first + cutSegment.second.first) / 2,
        (cutSegment.first.second + cutSegment.second.second) / 2));
}

int main()
{
    srand(time(NULL));

    fin >> nrVarfuri;

    if (nrVarfuri < 3)
    {
        fout << "Punctele introduse nu pot forma un poligon. Introduceti o valoare strict mai mare decat 3. \n";
        return 0;
    }

    poligon.resize(nrVarfuri);

    int contor = 1;
    for (auto& it : poligon)
    {
        fin >> it.first >> it.second;
        fout << "Punctul " << setw(2) << contor++ << " are coordonatele (" << setw(3) << it.first << ", " << setw(3) << it.second << ") \n";
    }

    if (nrVarfuri == 3)
    {
        if (Determinant(poligon[0], poligon[1], poligon[2]))
            fout << "Punctele introduse formeaza un triunghi. \n";
        else
            fout << "Punctele introduse nu formeaza un triunghi. \n";
        return 0;
    }

    for (int i = 0; i < nrVarfuri; i++)
    {
        for (int j = (i + 2) % nrVarfuri; (j + 1) % nrVarfuri != i; j = (j + 1) % nrVarfuri)
        {
            if (VerificareSegment(Segment(poligon[i], poligon[j])))
                triangulare.push_back({ min(i, j), max(i, j) }); // retinem indicii capetelor acelor puncte care formeaza segmentul (in ordine crescatoare)
        }
    }

    sort(triangulare.begin(), triangulare.end());

    contor = 1;
    fout << "\nIndicii varfurilor care formeaza segmentul respectiv: \n";
    for (auto& it : triangulare)
        fout << "Segmentul " << setw(2) << contor++ << " are ca si capete varfurile cu indicii " << setw(2) << it.first + 1 << ' ' << setw(2) << it.second + 1 << " \n";

    return 0;
}