Cod sursa(job #3213755)

Utilizator and_Turcu Andrei and_ Data 13 martie 2024 13:34:01
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <bits/stdc++.h>
#define N 120007
using namespace std;

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

#define int double
vector<pair<int,int>>a;
int n;
int32_t st[N];
bool viz[N];
int32_t top;

inline bool Determinant( pair<int,int>x,pair<int,int>y,pair<int,int>z )
{
    return (y.first*z.second -x.first*z.second -y.first*x.second -z.first*y.second +z.first*x.second +x.first*y.second)<=0;
}


int32_t main()
{
    fin >> n;
    for(int i=1;i<=n;i++)
    {
        pair<int,int>aux;
        fin >> aux.first >> aux.second ;
        a.push_back(aux);
    }
    sort(a.begin(),a.end());

    st[top]=0;
    st[++top]=1;
    viz[0]=1;
    viz[1]=1;

    /// index 0
    for(int32_t i=2;i<n;i++)
    {
        while( top>=1 and Determinant(a[st[top-1]],a[st[top]],a[i]) )
        {
            viz[ st[top] ]=0;
            top--;
        }
        st[++top]=i;
        viz[i]=1;
    }
    for(int32_t i=n-1;i>=0;i--)
        if( !viz[i] )
        {
            while( top>=1 and Determinant(a[st[top-1]],a[st[top]],a[i]) )
                top--;
            st[++top]=i;
        }



    fout << top+1 <<"\n";
    for(int i=0;i<=top;i++)
        fout << fixed << setprecision(6) << a[i].first << " " << a[i].second << "\n";
    return 0;
}