Cod sursa(job #2953841)

Utilizator LuxinMatMatasaru Luxin Gabriel LuxinMat Data 12 decembrie 2022 11:57:19
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

const int NMAX = 12e2;

struct ura
{
    double x, y;
} v[NMAX+1];

vector<ura> st;
int pmin;

double trig(ura a, ura b, ura c)
{
    return ((c.y-b.y)*(b.x-a.x) - (b.y-a.y)*(c.x-b.x)) > 0;
}

bool cmp(ura a, ura b)
{
    return trig(a, v[pmin], b) > 0;
}

int main()
{
    int n;
    cin>>n;
    v[0].y = 1e9;
    for(int i=1; i<=n; i++)
    {
        cin>>v[i].x>>v[i].y;
        if(v[pmin].y > v[i].y)
            pmin = i;
    }

    sort(v+1, v+n+1, cmp);

    st.push_back(v[1]);
    st.push_back(v[2]);
    for(int i=3; i<=n; i++)
    {
        int l = st.size();
        while(st.size() > 0 && trig(st[l-2], st[l-1], v[i]) > 0)
        {
            l--;
            st.pop_back();
        }
        st.push_back(v[i]);
    }
    cout<<st.size()<<'\n';
    for(int i=st.size()-1; i>=0; i--)
        cout<<st[i].x<<" "<<st[i].y<<"\n";
}