Cod sursa(job #2386405)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 22 martie 2019 19:28:30
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include<bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n;
struct xy
{
    double x;
    double y;
};
xy v[120005];
xy st[120005];
xy sol[120005];
int vf,lf;
bool cmp(xy a, xy b)
{
    if (a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}
xy jos, sus;
bool semn(xy a, xy b, xy c)
{
    return (a.x * c.y + c.x * b.y + a.y * b.x - b.x * c.y - a.x * b.y - c.x * a.y) < 0;
}
int main()
{
    in>>n;
    for (int i = 1; i <= n; ++i)
        in>>v[i].x>>v[i].y;
    sort(v + 1, v + n + 1,cmp);
    jos = v[1];
    sus = v[n];
    st[++vf] = v[1];
    for (int i = 2; i <= n; ++i)
    {
        while (vf > 1 && !semn(st[vf - 1],st[vf],v[i]))
            --vf;
        st[++vf] = v[i];
    }
    for (int i = 1; i <= vf; ++i)
        sol[i] = st[i];
    lf = vf;
    vf = 0;
    st[++vf] = v[n];
    for (int i = n - 1; i >= 1; --i)
    {
        while (vf > 1 && !semn(st[vf - 1],st[vf],v[i]))
            --vf;
        st[++vf] = v[i];
    }
    for (int i = 2; i <= vf; ++i)
        sol[i + lf - 1] = st[i];
    lf = lf + vf - 2;
    out<<lf<<"\n";
    out<<fixed<<setprecision(6);
    for (int i = 1; i <= lf; ++i)
    {
        out<<sol[i].x<<" "<<sol[i].y<<"\n";
    }
    return 0;
}