Cod sursa(job #2284392)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 17 noiembrie 2018 10:50:08
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX=12e4+5;

struct point
{
    double X, Y;
};

point A[NMAX];

int N, i, vf;

bool cmp (point A, point B)
{
    if(A.X > B. X || (A.X == B.X && A.Y > B.Y))
        return false;

    return true;
}

int Stiva[NMAX];

bool Sel[NMAX];

int Det (point A, point B, point 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);
}

int main()
{
    f.tie(NULL);

    f>>N;

    for(i=1; i<=N; ++i)
        f>>A[i].X>>A[i].Y;

    sort(A+1, A+N+1, cmp);

    Stiva[++vf]=1;

    Stiva[++vf]=2;
    Sel[2]=true;

    for(i=3; i<=N; ++i)
    {
        while(vf>=2 && Det(A[Stiva[vf-1]], A[Stiva[vf]], A[i]) < 0)
        {
            Sel[Stiva[vf]]=false;

            vf--;
        }

        Stiva[++vf]=i;
        Sel[i]=true;
    }

    for(i=N-1; i>=1; --i)
    {
        while(vf>=2 && !Sel[i] && Det(A[Stiva[vf-1]], A[Stiva[vf]], A[i]) < 0)
        {
            Sel[Stiva[vf]]=false;

            vf--;
        }

        Stiva[++vf]=i;
        Sel[i]=true;
    }

    g<<vf-1<<'\n';

    g<<setprecision(6)<<fixed;

    for(i=2; i<=vf; ++i)
        g<<A[Stiva[i]].X<<' '<<A[Stiva[i]].Y<<'\n';

    return 0;
}