Cod sursa(job #1651181)

Utilizator andrew_assassin789Andrei Manea andrew_assassin789 Data 12 martie 2016 16:57:13
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
#define pp pair<double,double>
#define w 120005
#define x first
#define y second
using namespace std;
inline double det(pp A,pp B,pp C)
{
    return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
pp v[w];
unsigned int st[w];
double eps=1e-12;
bool viz[w];
int main()
{
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
    int n,i,j,vf,k,l;double x,y;
    f>>n;
    for (i=1;i<=n;i++)
    {
        f>>x>>y;
        v[i]=make_pair(x,y);
    }
    sort(v+1,v+n+1);
    st[1]=1;st[2]=2;vf=2;
    i=0;j=1;viz[2]=1;
    do
    {
        if (i==n) j=-j;
        i+=j;
        if (viz[i]) continue;
        {
            l=st[vf-1];k=st[vf];
            while (vf>=2 && det(v[l],v[k],v[i])<eps)
            {
                viz[k]=0;
                vf--;
                l=st[vf-1];k=st[vf];
            }
            st[++vf]=i;viz[i]=1;
        }
    }
    while (i>0);
    g<<--vf<<'\n';
    g<<setprecision(6)<<fixed;
    for (i=1;i<=vf;i++)
    {
        g<<v[st[i]].x<<' '<<v[st[i]].y<<'\n';
    }
    f.close();
    g.close();
    return 0;
}