Cod sursa(job #1096641)

Utilizator SpiriFlaviuBerbecariu Flaviu SpiriFlaviu Data 2 februarie 2014 14:22:19
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
#include <fstream>
#include <algorithm>
#include <stack>
#include <iomanip>

using namespace std;

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

struct punct
{
    double x, y;
};

punct a[120001];
stack<punct> S;
stack<punct> AUX;
punct refp;

bool cmp(punct A, punct B)
{
    return (A.y-refp.y)*(B.x-refp.x) < (B.y-refp.y)*(A.x-refp.x);
}

int rotation(punct A, punct B, punct C)
{
    if(A.x == refp.x && A.y == refp.y )
        return true;
    if(B.y == refp.y && B.x == refp.x )
        return false;
    return (C.y - A.y)*(B.x - A.x) -  (C.x - A.x) * (B.y - A.y);
}

int main()
{
    int n;

    refp.x = 1000000000;
    refp.y = 1000000000;
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>a[i].x>>a[i].y;
        if(a[i].y < refp.y || (a[i].y < refp.y && a[i].x < refp.x ))
            refp = a[i];
    }
    sort(a+1,a+1+n,cmp);
    S.push(refp);
    S.push(a[2]);
    //S.push(a[3]);
    for(int i=3;i<=n;i++)
    {
        bool gata;
        do
        {
            gata = true;
            punct y = S.top();
            S.pop();
            punct x = S.top();
            if(rotation(x,y,a[i]) < 0)
            {
                gata = false;
            }
            else
            {
                S.push(y);
            }
        }while(!gata && S.size() >= 3);
        S.push(a[i]);
    }
    fout<<S.size()<<'\n';
    while(!S.empty())
    {
        AUX.push(S.top());
        S.pop();
    }
    while(!AUX.empty())
    {
        punct p = AUX.top();
        fout<<setprecision(6)<<fixed<<p.x<<' '<<p.y<<'\n';
        AUX.pop();

    }


    fin.close();
    fout.close();
    return 0;
}