Cod sursa(job #3248151)

Utilizator AlexTrTrambitas Alexandru-Luca AlexTr Data 10 octombrie 2024 21:40:52
Problema Gradina Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.55 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream f("gradina.in");
ofstream g("gradina.out");

const int NMAX = 250;

struct punct {
    double x, y;
    int parte;
} puncte[NMAX + 1], a, b, infas[NMAX + 1];


int Ion[NMAX + 1], Vasile[NMAX + 1], n, ci, cv, st[NMAX + 1];


bool cmp(punct P1, punct P2)
{
    if (P1.x > P2.x)
        return false;
    if (P1.x == P2.x)
        if (P1.y > P2.y)
            return false;

    return true;
}

double arie (punct P1, punct P2, punct P3)
{
    return (P1.x*P2.y + P2.x*P3.y + P3.x*P1.y - P2.y*P3.x - P3.y*P1.x - P1.y*P2.x); /// daca <0 => P3 e sub semiplan
                                                                                    /// daca >0 => P3 e peste semiplan
}

void infasuratoare(int v[NMAX + 1], int length)
{
    int k=0, ck;
    for (int i = 1; i<=length; ++i)
    {
        infas[i].x = puncte[v[i]].x;
        infas[i].y = puncte[v[i]].y;
    }
    /*for (int i = 1; i<=length; ++i)
        cout << infas[i].x << ' ' << infas[i].y << '\n';
    cout << endl;*/

    for (int i = 2; i<=length-1; ++i)
        if (arie(infas[1], infas[length], infas[i]) < 0)
            infas[i].parte = 1;
        else
            infas[i].parte = 2;

    st[1] = 1;
    k = 1;
    for (int i = 1; i<=length; ++i)
    {
        if (infas[i].parte == 1)
            ///cout << puncte[st[i]].x << ' ' << puncte[st[i]].y << '\n';
    }
    cout << endl;

    for (int i = 2; i<=length; ++i)
        if (infas[i].parte == 1 || infas[i].parte == 0)
        {
            while (k>1 && arie(infas[st[k-1]], infas[st[k]], infas[i]) < 0)
                --k;
            st[++k] = i;
        }

    ck = k;
    st[k] = length;
    for (int i = length-1; i>=1; --i)
        if (infas[i].parte == 2 || infas[i].parte == 0)
        {
            while (k>ck && arie(infas[st[k-1]], infas[st[k]], infas[i]) < 0)
                --k;
            st[++k] = i;
        }
    for (int i = 1; i<=k-1; ++i)
        ///cout << puncte[st[i]].x << ' ' << puncte[st[i]].y << '\n';
        ///cout << st[i] << ' ';
    cout << endl;
}

int main()
{
    f >> n;
    for (int i = 1; i<=n; ++i)
        f >> puncte[i].x >> puncte[i].y;

    sort(puncte + 1, puncte + n + 1, cmp);

    /*for (int i = 1; i<=n; ++i)
        cout << puncte[i].x << ' ' << puncte[i].y << endl;*/

    for (int i = 1; i<=n; ++i)
        for (int j = 1; j<=n; ++j)
        {
            if (i!=j)
            {
                a = puncte[i];
                b = puncte[j];
                ci = 0;
                cv = 0;
                for (int k = 1; k<=n; ++k)
                {
                    if (arie(a, b, puncte[k]) < 0)
                        puncte[k].parte = 1;
                    else
                        puncte[k].parte = 2;
                }
                for (int k = 1; k<=n; ++k)
                {
                    if (k == i)
                        Ion[++ci] = k;
                    else if (k == j)
                        Vasile[++cv] = k;
                    else
                    {
                        if (puncte[k].parte == 1)
                            Ion[++ci] = k;
                        else
                            Vasile[++cv] = k;
                    }
                }
                /*for (int i = 1; i<=ci; ++i)
                    cout << Ion[i] << ' ';
                cout << endl;*/
                infasuratoare(Ion, ci);

            }

        }

    return 0;
}