Cod sursa(job #2106312)

Utilizator papinub2Papa Valentin papinub2 Data 15 ianuarie 2018 16:43:19
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.22 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <queue>

using namespace std;

ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");

const int Nmax = 120005;

int n, varf, nod;
bool viz[Nmax];

struct punct
{
    double x;
    double y;
}v[Nmax];

vector<int> Q(Nmax);
vector<int> R(Nmax);

int intoarcere (punct P0, punct P1, punct P2)
{
    return (P1.x - P0.x) * (P2.y - P0.y) - (P2.x - P0.x) * (P1.y - P0.y);
}

bool cmp(punct A,punct B)
{
     if(A.y == B.y)return A.x < B.x;
    return A.y < B.y;
}


int main()
{
    in >> n;

    for (int i = 1; i <= n; i++)
        in >> v[i].x >> v[i].y;

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

    Q[++varf] = 1;
    Q[++varf] = 2;

    viz[1] = 1;
    viz[2] = 1;

    for (int i = 3; i <= n; i++)
    {
        int val = intoarcere (v[Q[varf - 1]], v[Q[varf]], v[i]);

        if (val == 0)
        {
            viz[Q[varf]] = 0;
            varf--;

            Q[++varf] = i;
            viz[i] = 1;
        }

        else

        if (val > 0)
        Q[++varf] = i, viz[i] = 1;

        else

        {
            while (val <= 0 && varf > 1)
            {
                viz[Q[varf]] = 0;
                varf--;
                val = intoarcere(v[Q[varf - 1]], v[Q[varf]], v[i]);
            }

            Q[++varf] = i;
            viz[i] = 1;
        }
    }

    for (int i = n - 1; i >= 1; i--)
    {
        if (viz[i] == 1) continue;

        int val = intoarcere (v[Q[varf - 1]], v[Q[varf]], v[i]);

        if (val == 0)
        {
            viz[Q[varf]] = 0;
            varf--;

            Q[++varf] = i;
            viz[i] = 1;
        }

        else

        if (val > 0)
        Q[++varf] = i, viz[i] = 1;

        else

        {
            while (val <= 0 && varf > 1)
            {
                viz[Q[varf]] = 0;
                varf--;
                val = intoarcere(v[Q[varf - 1]], v[Q[varf]], v[i]);
            }

            Q[++varf] = i;
            viz[i] = 1;
        }
    }


    out << varf << '\n';
    for (int i = 1; i <= varf; i++)
        out << fixed << setprecision(12) << v[Q[i]].x << ' ' << v[Q[i]].y << '\n';
}