Cod sursa(job #1829844)

Utilizator alexilasiAlex Ilasi alexilasi Data 15 decembrie 2016 18:44:02
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.39 kb
#include <fstream>
#include <stack>
#include <algorithm>

using namespace std;

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

int n,i,l,A,B;
struct punct
{
    double x,y;
    int o;
} p[120001],pa,pb;

int compare(punct a,punct b)
{
    return (a.y<b.y);
}
stack <punct> s,S;

double determinant(punct A,punct B,punct C)
{
    return A.x * B.y  + B.x * C.y + C.x * A.y - C.x * B.y - A.x * C.y - B.x * A.y;
}

int sensTriunghi(punct A,punct B,punct C)
{
    if (determinant(A,B,C) < 0)
    {
        return -1;
    }
    else
    {
        return 1;
    }
}


int main()
{
    fin>>n;
    for(i=1; i<=n; i++)
    {
        fin>>p[i].x>>p[i].y;

    }
    sort(p+1,p+n+1,compare);
    for(i=1; i<=n; i++) p[i].o=i;
    s.push(p[1]);
    s.push(p[2]);
    l=2;
    for(i=3; i<=n; i++)
    {
        pa=s.top();
        s.pop();
        pb=s.top();
        s.push(pa);
        if(sensTriunghi(pb,pa,p[i])==1)s.push(p[i]),l++;
        else
        {
            while(sensTriunghi(pb,pa,p[i])!=1&&l>1)
            {
                s.pop();
                l--;
                if(l!=1)
                {
                    pa=s.top();
                    s.pop();
                    pb=s.top();
                    s.push(pa);
                }
            }
            s.push(p[i]);
            l++;
        }
    }

    S.push(p[1]);
    S.push(p[2]);
    l=2;
    for(i=3; i<=n; i++)
    {
        pa=S.top();
        S.pop();
        pb=S.top();
        S.push(pa);
        if(sensTriunghi(pb,pa,p[i])==-1)S.push(p[i]),l++;
        else
        {
            while(sensTriunghi(pb,pa,p[i])!=-1&&l>1)
            {
                S.pop();
                l--;
                if(l!=1)
                {
                    pa=S.top();
                    S.pop();
                    pb=S.top();
                    S.push(pa);
                }
            }
            S.push(p[i]);
            l++;
        }
    }
    int h=0;
    fout<<s.size()+S.size()-2<<'\n';
    while(!s.empty())
    {
        p[++h]=s.top();
        s.pop();
    }
    for(h=h;h>0;h--)
        fout<<p[h].x<<" "<<p[h].y<<'\n';

    while(!S.empty())
    {
        p[++h]=S.top();
        S.pop();
    }
    for(i=2;i<h;i++)
        fout<<p[i].x<<" "<<p[i].y<<'\n';
    fin.close();
    fout.close();
    return 0;
}