Cod sursa(job #897470)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 27 februarie 2013 20:52:44
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <iomanip>

#define DN 120005
#define x first
#define y second
#define per pair<double,double>
using namespace std;

per p[DN];
stack< per > st;


double ccw( per p1,per p2,per p3)
{
    return (p2.x-p1.x)*(p3.y-p1.y) - (p2.y-p1.y) *( p3.x - p1.x );
}
int cmp(per p1,per p2)
{
    return ccw(p[1],p1,p2) < 0;
}

int main()
{
    int n;
    ifstream f("infasuratoare.in");
    ofstream g("infasuratoare.out");
    f>>n;
    int poz=1;
    for(int i=1;i<=n;++i)
    {
        f>>p[i].x>>p[i].y;
        if(p[i]<p[poz])
            poz=i;
    }

    swap(p[1],p[poz]);

    sort(p+2,p+n+1,cmp);

    st.push(p[1]);
    st.push(p[2]);

    for(int i=3;i<=n;++i)
    {
        bool ok = true;
        while(st.size()>=2 && ok)
        {
            per first=st.top();
            st.pop();

            if( ccw(st.top(),first,p[i]) <= 0 )
                st.push(first),ok=false;// il punem la loc

        }
        st.push(p[i]);
    }

    g<<fixed<<st.size()<<"\n";
    while(st.size())
    {
        g<<setprecision(6)<<st.top().x<<" "<<st.top().y<<"\n";
        st.pop();
    }
    return 0;
}