Cod sursa(job #2254534)

Utilizator gavra_bogdanBogdan Gavra gavra_bogdan Data 5 octombrie 2018 15:11:18
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <bits/stdc++.h>

using namespace std;
const int nmax=120005;
const double eps=0.000000000001;
pair<double,double> v[nmax];
stack<int>st;
stack<int>afis;
bool f[nmax];
bool is_st(pair<double,double> a,pair<double,double> b,pair<double,double> c)
{
    if((c.second*(b.first-a.first)+c.first*(a.second-b.second)+b.second*a.first-a.second*b.first)<eps)
        return 1;
    return 0;
}
int main()
{
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>v[i].second>>v[i].first;
    sort(v+1,v+n+1);
    st.push(1);
    st.push(2);
    f[2]=true;
    int sign=1;
    for(int i=3; i; i+=sign)
    {
        if(f[i]==true)
            continue;
        int a,b;
        while(st.size()>1)
        {
            f[st.top()] = false;
            b=st.top();
            st.pop();
            a=st.top();
            if(is_st(v[a],v[b],v[i]))
            {
                st.push(b);
                f[st.top()] = true;
                break;
            }
        }
        st.push(i);
        f[st.top()] = true;
        if(st.top()==n)
            sign=-1;
    }
    st.pop();
    while(!st.empty())
    {
        afis.push(st.top());
        st.pop();
    }
    cout<<afis.size()<<"\n";
    cout << setprecision(12) << fixed;
    while(!afis.empty())
    {
        int t=afis.top();
        cout<<v[t].second<<" "<<v[t].first<<"\n";
        afis.pop();
    }
    return 0;
}