Cod sursa(job #2284430)

Utilizator hprecupPrecup Horea hprecup Data 17 noiembrie 2018 10:58:55
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb
#include <iostream>
#include<fstream>
#include<algorithm>
#include<iomanip>
using namespace std;

#define pp pair< double, double >
#define x first
#define y second

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

int i,n,st[120010],niv,val,aux;
pp v[120010];

double determinant(pp a, pp b, pp c)
{
    int ans=a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-a.y*b.x;
    return ans;
}

int main()
{
    fin>>n;
    for(i=1; i<=n; i++)
    {
        fin>>v[i].x>>v[i].y;
    }
    sort(v+1, v+n+1);
    st[1]=1; st[2]=2; niv=3;
    for(i=3; i<=n; i++)
    {
        val=determinant(v[st[niv-2]],v[st[niv-1]],v[i]);
        if(val>=0)
        {
            st[niv]=i;
            niv++;
        }
        else
        {
            if(niv==3)
            {
                st[2]=i;
            }
            else
            {
                while(val<0 && niv>2)
                {
                    niv--;
                    val=determinant(v[st[niv-2]],v[st[niv-1]],v[i]);
                }
                st[niv]=i;
                niv++;
            }
        }
    }
    aux=niv-1;
    st[niv]=n-1;
    niv++;
    for(i=n-2; i>=1; i--)
    {
        val=determinant(v[st[niv-2]],v[st[niv-1]],v[i]);
        if(val>=0)
        {
            st[niv]=i;
            niv++;
        }
        else
        {
            if(niv-aux==2)
            {
                st[niv-1]=i;
            }
            else
            {
                while(val<0 && niv>aux+1)
                {
                    niv--;
                    val=determinant(v[st[niv-2]],v[st[niv-1]],v[i]);
                }
                st[niv]=i;
                niv++;
            }
        }

    }
    niv--;
    fout<<niv-1<<'\n';
    for(i=2; i<=aux; i++)
        fout<<setprecision(6)<<fixed<<v[st[i]].x<<" "<<v[st[i]].y<<'\n';
    for(i=aux+1; i<=niv; i++)
        fout<<setprecision(6)<<fixed<<v[st[i]].x<<" "<<v[st[i]].y<<'\n';
    return 0;
}