Cod sursa(job #2284453)

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

using namespace std;

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

const int NMAX=12e4+100;

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];

long long 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; i>=1; --i)
    {
        if(!Sel[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=vf-1; i>=1; --i)
        g<<A[Stiva[i]].X<<' '<<A[Stiva[i]].Y<<'\n';

    return 0;
}