Cod sursa(job #2955552)

Utilizator LuxinMatMatasaru Luxin Gabriel LuxinMat Data 17 decembrie 2022 12:46:09
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include<fstream>
#include<algorithm>
#include<vector>
#include<iomanip>
using namespace std;

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

const int NMAX = 120000;

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

vector<ura> st;
int pmin;

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

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

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

    swap(v[0], v[pmin]);
    sort(v+1, v+n, cmp);

    st.push_back(v[0]);
    st.push_back(v[1]);
    for(int i=2; i<n; i++)
    {
        int l = st.size();
        while(st.size() >= 2 && 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=0; i<st.size(); i++)
        cout<<fixed<<setprecision(6)<<st[i].x<<" "<<st[i].y<<"\n";
}