Cod sursa(job #2384822)

Utilizator moltComan Calin molt Data 21 martie 2019 10:53:50
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 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];
vector<xy> sol;
int vf;

bool cmp(xy a, xy b)
{
    if (a.y < b.y) return true;
    if (a.y == b.y) return a.x < b.y;
    return false;
}

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 > 0 && semn(st[vf - 1],st[vf],v[i]))
                --vf;
            st[++vf] = v[i];}

    //for (int i = 1;i <= vf;++i) out<<st[i].x<<" "<<st[i].y<<"\n";

    for (int i = 1;i <= vf;++i) sol.push_back(st[i]);
    vf = 0;
    st[++vf] = v[n];
    for (int i = n - 1;i >= 1;--i)
            {while (vf > 0 && !semn(st[vf],st[vf - 1],v[i]))
                  --vf;
            st[++vf] = v[i];}
    for (int i = 2;i <= vf;++i) sol.push_back(st[i]);
    out<<sol.size()<<"\n";
    for (vector<xy> :: reverse_iterator it = sol.rbegin(); it != sol.rend();++it)
    {out<<fixed<<setprecision(6);
          out<<it -> x<<" "<<it -> y<<"\n";}

    return 0;
}