Cod sursa(job #3246389)

Utilizator AlexTrTrambitas Alexandru-Luca AlexTr Data 2 octombrie 2024 20:41:47
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.2 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

const int NMAX = 120000;

struct punct {
    float x, y;
} puncte[NMAX + 1], jos[NMAX + 1], sus[NMAX + 1], st1[NMAX + 1], st2[NMAX + 1];

int n, kj, ks, k1, k2;

void afis(punct v[NMAX + 1], int length)
{
    for (int i = 1; i<=length; ++i)
        g << v[i].x << ' ' << v[i].y << '\n';
}

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;
}

float 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
}

int valid(int e, int sgn)
    {
        if (sgn == -1)
            return e<0;
        else
            return e>0;
    }

void solve(punct v[NMAX + 1], int length, punct st[NMAX + 1], int &k, int sgn)
{
    if (sgn == -1)
    {
        st[++k] = v[1];
        for (int i = 2; i <= length; ++i)
        {
            while ( k>1 && valid(arie(st[k-1], st[k], v[i]), sgn))
                --k;
            st[++k] = v[i];
        }
    }
    else
    {
        st[++k] = v[length];
        for (int i = length-1; i >=1 ; --i)
        {
            while ( k>1 && !valid(arie(st[k-1], st[k], v[i]), sgn))
                --k;
            st[++k] = v[i];
        }
    }
}

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 = 2; i<=n-1; ++i)
        if (arie(puncte[1], puncte[n], puncte[i]) < 0)
            jos[++kj] = puncte[i];
        else
            if (arie(puncte[1], puncte[n], puncte[i]) > 0)
                sus[++ks] = puncte[i];

    st1[++k1] = puncte[1];
    solve(jos,kj, st1, k1, -1);
    st2[++k2] = puncte[n];
    solve(sus, ks, st2, k2, 1);
    g << k1+k2 << '\n';

    afis(st1, k1);
    afis(st2, k2);
///afis(puncte, n);

    return 0;
}