Cod sursa(job #2757313)

Utilizator NeuerRaducu Ioan Stefan Neuer Data 4 iunie 2021 23:02:34
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb

#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
const int SIZE = 130000;

using namespace std;

typedef long double ld;

struct punct
{
    ld y, x;
    bool operator < (const punct &other) const
    {
        if(y==other.y) return x<other.x;
        return y<other.y;
    }
};

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

punct v[SIZE];
vector <int> st;
int n;

void readit()
{
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>v[i].y>>v[i].x;
}

double deter(punct a, punct b, punct c)
{
    return a.x*b.y+b.x*c.y+c.x*a.y
          -b.y*c.x-a.y*b.x-a.x*c.y;
}

bool cmp(punct a, punct b)
{
    return (deter(v[1], a, b)<0);
}

void sortPoints()
{
    int ind=1;
    for(int i=2; i<=n; i++)
        if(!(v[ind]<v[i])) ind=i;
    swap(v[1], v[ind]);
    sort(v+2, v+n+1, cmp);
}

void convex_hull()
{
    sortPoints();
    st.push_back(1), st.push_back(2);
    for(int i=3; i<=n; i++)
    {
        while(st.size()>=2 && deter(v[st.back()], v[st[st.size()-2]], v[i])<0)
            st.pop_back();
        st.push_back(i);
    }
}

void afis()
{
    cout<<st.size()<<'\n';
    for(int i=1; i<st.size(); i++)
        cout<<setprecision(9)<<v[st[i]].y<<' '<<v[st[i]].x<<'\n';
    cout<<setprecision(9)<<v[1].y<<' '<<v[1].x<<'\n';
}

int main()
{
    readit();
    convex_hull();
    afis();
    return 0;
}