Cod sursa(job #2528024)

Utilizator Mihai_EduardMihai Eduard Mihai_Eduard Data 21 ianuarie 2020 12:26:51
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.99 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;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;
        }
    }
    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]);
        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;
                }
            }
        }
    }
    st.push(v[1]);
    fout<<st.size()-1<<endl;
    while(st.size()>1)
    {
        a=st.top();
        fout<<fixed<<setprecision(12)<<a.x<<' '<<a.y<<endl;
        st.pop();
    }

}