Cod sursa(job #2165852)

Utilizator Tataru_AdelinTataru Adelin Tataru_Adelin Data 13 martie 2018 14:02:11
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.25 kb
#include <bits/stdc++.h>

using namespace std;

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

class Dot
{
private:
    double x;
    double y;
    double angle;
public:
    Dot(void)
    {}
    Dot(double X,double Y): x(X),y(Y)
    {}

    double GetX(void)
    {
        return x;
    }

    double GetY(void)
    {
        return y;
    }

    double GetAngle(void)
    {
        return angle;
    }

    void SetXY(double X,double Y)
    {
        x=X;
        y=Y;
    }

    void SetAngle(Dot a)
    {
        angle=(x-a.GetX())/sqrt((x-a.GetX())*(x-a.GetX())+(y-a.GetY())*(y-a.GetY()));
    }
};

bool comp(Dot a, Dot b)
{
    return a.GetAngle()>b.GetAngle();
}

double Det(Dot a, Dot b, Dot c)
{
    return a.GetX()*(b.GetY()-c.GetY())+b.GetX()*(c.GetY()-a.GetY())+c.GetX()*(a.GetY()-b.GetY());
}

int main()
{
    int number_of_dots,coord=0;
    double x,y;
    fin>>number_of_dots;
    vector<Dot> dots(number_of_dots);
    fin>>x>>y;
    Dot lowest_dot(x,y);
    dots[0]=lowest_dot;
    for(int i=1;i<number_of_dots;i++)
    {
        fin>>x>>y;
        dots[i].SetXY(x,y);
        if(dots[i].GetY()<lowest_dot.GetY())
        {
            lowest_dot=dots[i];
            coord=i;
        }
        else
            if(dots[i].GetY()==lowest_dot.GetY() && dots[i].GetX()<lowest_dot.GetX())
            {
                lowest_dot=dots[i];
                coord=i;
            }
    }
    swap(dots[0],dots[coord]);

    for(int i=1;i<number_of_dots;i++)
        dots[i].SetAngle(lowest_dot);

    sort(dots.begin()+1,dots.end(),comp);

    Dot past,now,next;

    stack<Dot> stk;

    past=dots[0];
    now=dots[1];

    stk.push(past);
    stk.push(now);

    for(int i=2;i<number_of_dots;i++)
    {
        next=dots[i];
        while(Det(past,now,next)<0)
        {
            stk.pop();
            now=stk.top();
            stk.pop();
            past=stk.top();
            stk.push(now);
        }
        stk.push(next);
        past=now;
        now=next;
    }

    fout<<stk.size()<<'\n';
    stack<Dot>aux;
    while(stk.size())
    {
        aux.push(stk.top());
        stk.pop();
    }
    while(aux.size())
    {
        now=aux.top();
        fout<<fixed<<setprecision(7)<<now.GetX()<<' '<<now.GetY()<<'\n';
        aux.pop();
    }


    return 0;
}