Cod sursa(job #2528033)

Utilizator Mihai_EduardMihai Eduard Mihai_Eduard Data 21 ianuarie 2020 12:43:27
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.96 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
    float x, y;
    int ord;
} v[120001];
bool comp(punct A, punct B)
{
    if(A.y==B.y)
        return A.x<B.x;
    return A.y<B.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-a.y*b.x-c.y*a.x;
}
stack <punct> st;
int t[120001], n;
int main()
{
    punct a, b, c;
    fin>>n;
    for(int i=1; i<=n; i++)
    {
        fin>>v[i].x>>v[i].y;
    }
    sort(v+1,v+1+n,comp);
    for(int i=1; i<=n; i++)
        v[i].ord=i;
    st.push(v[1]);
    st.push(v[2]);
    t[1]=1;
    t[2]=1;
    for(int i=3; i<=n-1; i++)
    {
        b=st.top();
        st.pop();
        a=st.top();
        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;
        }
    }
    b=st.top();
    st.pop();
    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)
    {
        st.push(v[j]);
        t[j]=1;
        for(int i=j-1; i>1; i--)
        {
            if(t[i]==0)
            {
                b=st.top();
                st.pop();
                a=st.top();
                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;
                }
            }
        }
    }
    b=st.top();
    st.pop();
    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<<fixed<<setprecision(12)<<v[1].x<<' '<<v[1].y<<endl;
    while(st.size()>1)
    {
        a=st.top();
        fout<<fixed<<setprecision(12)<<a.x<<' '<<a.y<<endl;
        st.pop();
    }

}