Cod sursa(job #2159103)

Utilizator moltComan Calin molt Data 10 martie 2018 19:05:51
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;

const int NMAX = 120001;

struct pct{double x,y;};

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

bool cmp(pct a,pct b)
{
    return (a.x < b.x && a.y < b.y);
}

bool semn(pct a,pct b,pct c)
{
    //return (a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - c.y * a.x - a.y * b.x) < 0;
    return (b.x*a.y+c.x*b.y+a.x*c.y-a.x*b.y-b.x*c.y-c.x*a.y)<0;
}

int n,vf,lf;
pct v[NMAX],st[NMAX],sol[NMAX];

int main()
{
    in>>n;
    for (int i = 0;i < n;++i)
         in>>v[i].x>>v[i].y;
    sort(v,v + n,cmp);
    st[++vf] = v[0];
    for (int i = 1;i < n;++i)
    {
        while (vf > 1 && semn(st[vf - 1],st[vf],v[i]) == 0)
              --vf;
        st[++vf] = v[i];
    }
    lf = vf;
    for (int i = 1;i <= vf;++i)
        sol[i] = st[i];
    vf = 0;
    st[++vf] = v[n - 1];
    for (int i = n - 2;i >= 0;--i)
         {while (vf > 1 && semn(st[vf - 1],st[vf],v[i]) == 0)
                --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";
    for (int i = 1;i <= lf;++i)
         out<<fixed<<setprecision(6)<<sol[i].x<<" "<<sol[i].y<<"\n";
    return 0;
}