Cod sursa(job #3245327)

Utilizator Cosmin1234Creanga Cosmin Andrei Cosmin1234 Data 28 septembrie 2024 15:03:59
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.34 kb
#include <fstream>
#include <stack>
#include <algorithm>
#include <iomanip>

using namespace std;

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

struct punct
{
    float x, y;
    int poz;
}v[120000];

bool cmp(punct a, punct b)
{
    if (a.x < b.x)
        return true;
    else if (a.x > b.x)
        return false;
    else
        return (a.y < b.y);
}

double arie(punct a, punct b, punct c)
{
    return a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - c.y * a.x - a.y * b.x;
}

int st[120000], vf;
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i].x>>v[i].y;
    }
    sort(v+1, v+n+1, cmp);
    for(int i=2;i<n;i++)
    {
        if(arie(v[1], v[n], v[i]) < 0)
            v[i].poz = 1;
        else
            v[i].poz = -1;
    }
    //jos( -1 )
    st[1] = 1;
    vf=1;
    for(int i=2;i<n;i++)
    {
        if(v[i].poz == 1)
        {
            if(st[vf] == 1)
                st[++vf] = i;
            else
            {
                bool ok = true;
                while(st[vf] != 1 && ok == true)
                {
                    if(arie(v[st[vf-1]], v[st[vf]], v[i]) < 0)
                        vf--;
                    else
                    {
                        ok = false;
                        st[++vf] = i;
                    }
                }
                if(ok == true)
                    st[++vf] = i;
            }
        }
    }
    //sus( 1 )
    st[++vf] = n;
    for(int i=n-1;i>1;i--)
    {
        if(v[i].poz == -1)
        {
            if(st[vf] == n)
                st[++vf] = i;
            else
            {
                bool ok = true;
                while(st[vf] != n && ok == true)
                {
                    if(arie(v[st[vf-1]], v[st[vf]], v[i]) < 0)
                        vf--;
                    else
                    {
                        ok = false;
                        st[++vf] = i;
                    }
                }
                if(ok == true)
                    st[++vf] = i;
            }
        }
    }
    for (int i=2; i<=vf; i++)
        cout << fixed << setprecision(6) << v[st[i]].x << " " << v[st[i]].y << '\n';
    cout << fixed << setprecision(6) << v[st[1]].x << " " << v[st[1]].y << '\n';
    return 0;
}