Cod sursa(job #1922180)

Utilizator caprariuapCaprariu Alin-Paul caprariuap Data 10 martie 2017 16:17:56
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>
#include <iomanip>

using namespace std;

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

struct punct
{
    double x,y;
} a[120010],minim,st[120010];

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(a[1],A,B)<0;
    }
};

int n,i,j,vf,poz;

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