Cod sursa(job #1969821)

Utilizator caprariuapCaprariu Alin-Paul caprariuap Data 18 aprilie 2017 17:48:33
Problema Infasuratoare convexa Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>
#include <iomanip>
#include <queue>
using namespace std;

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

#define nmax 120010

struct punct
{
    long double x,y;
}v[nmax],stk[nmax],minim;

int n,i,vf;

long double cp(punct A, punct B, punct C)
{
    return (B.y-A.y)*(C.x-A.x)-(C.y-A.y)*(B.x-A.x);
}

class cmp
{
public:
    bool operator()(punct A, punct B)
    {
        return cp(v[1],A,B)<0;
    }
};

int main()
{
    fin >> n;
    for (i=1; i<=n; i++)
    {
        fin >> v[i].x >> v[i].y;
        if (v[i].x<v[1].x||(v[i].x==v[1].x&&v[i].y<v[1].y))
            swap(v[1],v[i]);
    }
    sort(v+2,v+n+1,cmp());
    stk[++vf]=v[1];
    stk[++vf]=v[2];
    for (i=3; i<=n; i++)
    {
        while (vf>0&&cp(stk[vf-1],stk[vf],v[i])>0)
            vf--;
        stk[++vf]=v[i];
    }
    fout << vf << '\n';
    for (i=1; i<=vf; i++)
        fout << fixed << setprecision(12) << stk[i].x << ' ' << stk[i].y << '\n';
}