Cod sursa(job #2295788)

Utilizator Tataru_AdelinTataru Adelin Tataru_Adelin Data 3 decembrie 2018 22:33:35
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <bits/stdc++.h>

using namespace std;


class Dot
{
public:
    double x,y;
    double angle;
private:
    /// functions
public:
    void setAngle(Dot a)
    {
        if (a.x != x)
            angle = (a.y - y) / (a.x - x);
        else
            angle = numeric_limits<double>::infinity();
    }

    Dot()
    {}

    Dot(double a, double b)
    {
        x=a;
        y=b;
    }

    ~Dot()
    {}
private:


};

bool comp(Dot a, Dot b)
{
    return a.angle < b.angle;
}

double det(Dot a1, Dot a2, Dot a3)
{
    return (a2.x - a1.x) * (a3.y - a1.y) - (a2.y - a1.y) * (a3.x - a1.x);
}

vector <Dot> makeConvexHull(vector <Dot> &dots, int n)
{
    vector <Dot> stk;

    stk.push_back(dots[0]);
    stk.push_back(dots[1]);

    for(int i = 2; i <= n; i++)
    {
        while(det(stk[stk.size() - 2], stk[stk.size() - 1], dots[i]) < 0)
        {
            stk.pop_back();
        }

        stk.push_back(dots[i]);

    }

    return stk;

}

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

int main()
{
    int start_index = 0;
    int n;
    double x, y;
    fin>>n;
    vector <Dot> dots(n + 1);

    for(int i = 0; i < n; i++)
    {
        fin>>x>>y;
        dots[i] = Dot(x, y);
        if(dots[i].x <= dots[start_index].x)
        {
            if(dots[i].x == dots[start_index].x && dots[i].y < dots[start_index].y)
                start_index = i;
            else if(dots[i].x < dots[start_index].x)
                start_index = i;
        }
    }
    swap(dots[0], dots[start_index]);

    for(int i = 1; i < n; i++)
       dots[i].setAngle(dots[0]);

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

    dots[n] = dots[0];

    vector <Dot> ans = makeConvexHull(dots, n);

    fout<<ans.size() - 1<<'\n';

    for(unsigned i = 1; i < ans.size(); i++)
        fout<<setprecision(7)<<fixed<<ans[i].x<<' '<<ans[i].y<<'\n';


    return 0;
}