Cod sursa(job #2527815)

Utilizator grigorut_octavianGrigorut Dominic Octavian grigorut_octavian Data 20 ianuarie 2020 21:31:40
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.26 kb
#include <bits/stdc++.h>

using namespace std;

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

struct punct
{
    int ord;
    double x,y;
} v[120001];

stack<punct> st;

bool compara(punct vs,punct vd)
{
    if(vd.y==vs.y) return vs.x<vd.x;
    return vs.y<vd.y;
}

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


int main()
{
    int n;
    fin>>n;
    for(int i=1; i<=n; i++)
    {
        fin>>v[i].x>>v[i].y;
    }
    sort(v+1,v+1+n,compara);
    for(int i=1; i<=n; i++)
    {
        v[i].ord=i;
    }
    int t[120001]= {0};
    punct vf,baz;
    vf=v[n];
    baz=v[1];
    t[1]=1;
    st.push(baz);
    st.push(v[2]);
    t[2]=1;
    for(int i=3; i<=n-1; i++)
    {
        punct b=st.top();
        st.pop();
        punct a=st.top();
        punct c=v[i];
        if(calc_det(a,b,c)<=0)
        {
            st.push(b);
            st.push(c);
            t[c.ord]=1;
        }
        else
        {
            t[b.ord]=0;
            bool ok=true;
            while(ok==true and st.size()>1)
            {
                b=a;
                st.pop();
                a=st.top();
                if(calc_det(a,b,c)<=0)
                {
                    st.push(b);
                    ok=false;
                }
                else
                {
                    t[b.ord]=0;
                }
            }
            st.push(c);
            t[c.ord]=1;
        }
    }
    punct b=st.top();
    st.pop();
    punct a=st.top();
    if(calc_det(a,b,v[n])<=0)
    {
        st.push(b);
        st.push(v[n]);
        t[n]=1;
    }
    else
    {
        bool ok=true;
        while(ok==true and st.size()>1)
        {
            t[b.ord]=0;
            b=a;
            st.pop();
            a=st.top();
            if(calc_det(a,b,v[n])<=0)
            {
                st.push(b);
                ok=false;
            }
        }
        st.push(v[n]);
        t[n]=1;
    }
    int j=-1;
    for(int i=n; i>1; i--)
    {
        if(t[i]==0)
        {
            j=i;
            break;
        }
    }
    if(j!=-1)
    {
        int siz=st.size();
        st.push(v[j]);
        punct d=st.top();
        t[j]=1;
        for(int i=j-1; i>1; i--)
        {
            if(t[i]==0)
            {
                punct b=st.top();
                st.pop();
                punct a=st.top();
                punct c=v[i];
                if(calc_det(a,b,c)<=0)
                {
                    st.push(b);
                    st.push(c);
                    t[c.ord]=1;
                }
                else
                {
                    t[b.ord]=0;
                    bool ok=true;
                    while(ok==true and st.size()>1)
                    {
                        b=a;
                        st.pop();
                        a=st.top();
                        if(calc_det(a,b,c)<=0)
                        {
                            st.push(b);
                            ok=false;
                        }
                        else
                        {
                            t[b.ord]=0;
                        }
                    }
                    st.push(c);
                    t[c.ord]=1;
                }
            }
        }
        punct b=st.top();
        st.pop();
        punct a=st.top();
        if(calc_det(a,b,v[1])<=0)
        {
            st.push(b);
        }
        else
        {
            bool ok=true;
            while(ok==true and st.size()>1)
            {
                t[b.ord]=0;
                b=a;
                st.pop();
                a=st.top();
                if(calc_det(a,b,v[1])<=0)
                {
                    st.push(b);
                    ok=false;
                }
            }

        }

    }
    fout<<st.size()<<endl;
    fout<< std::setprecision(12)<<v[1].x<<' ';
    fout<< std::setprecision(12)<<v[1].y<<endl;
    while(st.size()>1)
    {
        punct x1=st.top();
        st.pop();
        fout<< std::setprecision(12)<<x1.x<< ' ';
        fout<< std::setprecision(12)<<x1.y<<endl;
    }
    return 0;
}