Cod sursa(job #2158313)

Utilizator andreeagoideaAndreea Goidea andreeagoidea Data 10 martie 2018 11:56:28
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.76 kb
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <fstream>

using namespace std;

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

struct punct
{
    double x, y;
    int q;
}v[120001];

int n, nrsol, nrtot;
int st[120001];

bool cmp(punct a, punct b)
{
    if(a.y<b.y)
        return true;
    if(a.y==b.y && a.x<b.x)
        return true;
    return false;
}

int stanga(int a, int b, int c)
{
    double arie=v[a].x*v[b].y+v[b].x*v[c].y+v[c].x*v[a].y-v[b].x*v[a].y-v[c].x*v[b].y-v[a].x*v[c].y;
    if(arie<0)
        return 0;
    return 1;
}

void det_dreapta()
{
    int poz=0;
    st[1]=1;
    for(int i=2; i<=n && poz==0; i++)
    {
        if(stanga(1, n, i)==0)
        {
            poz=i+1;
            st[2]=i;
            v[i].q=1;
        }
    }
    nrsol=2;
    if(poz<=n)
    {
        for(int i=poz; i<n; i++)
        {
            if(stanga(1, n, i)==0)
            {
                v[i].q=1;
                if(stanga(st[nrsol-1], st[nrsol], i))
                {
                    nrsol++;
                    st[nrsol]=i;
                }
                else
                    {
                    while(stanga(st[nrsol-1], st[nrsol], i)==0 && nrsol>1)
                        nrsol--;
                    nrsol++;
                    st[nrsol]=i;
                }
            }
        }
        nrsol++;
        st[nrsol]=n;
    }

}

void det_stanga()
{
    int poz=0;
    for(int i=n-1; i>1; i--)
    {
        if(v[i].q==0)
        {
            poz=i+1;
            st[nrtot]=i;
        }
    }
    if(poz>1)
    {
        for(int i=poz; i>1; i--)
        {
            if(v[i].q==0)
            {
                if(stanga(st[nrtot], st[nrtot-1], i)==0)
                {
                    nrtot++;
                    st[nrtot]=i;
                }
                else
                {
                    while(stanga(st[nrtot], st[nrtot-1], i) && nrtot>nrsol)
                        nrtot--;
                    nrtot++;
                    st[nrtot]=i;
                }
            }
        }
    }
}

void afis()
{
    int poz=0;
    fout<<nrtot-1<<"\n";
    for(int i=1; i<=nrtot; i++)
    {
        if(v[st[i]].y<0)
            poz++;
        else
            fout<<fixed<<setprecision(6)<<v[st[i]].x<<" "<<v[st[i]].y<<"\n";
    }
    for(int i=1; i<poz; i++)
       fout<<fixed<<setprecision(6)<<v[st[i]].x<<" "<<v[st[i]].y<<"\n";
}

int main()
{
    fin>>n;
    for(int i=1; i<=n; i++)
    {
        fin>>v[i].x>>v[i].y;
        v[i].q=0;
    }
    sort(v+1, v+n+1, cmp);
    v[1].q=0;
    v[n].q=1;
    det_dreapta();
    nrtot=nrsol+1;
    det_stanga();
    afis();
    return 0;
}