Cod sursa(job #3221975)

Utilizator solicasolica solica solica Data 8 aprilie 2024 18:41:49
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.12 kb
#include <fstream>
#include <stack>
#include <stdlib.h>
#include <vector>
#include <algorithm>

using namespace std;

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

#define double long double

struct pt
{
    double x, y;
    bool operator == (pt const& t) const
    {
        return x == t.x && y == t.y;
    }
};

int n;

vector<pt>a;

int i;

int orientation(pt a, pt b, pt c)
{
    double v = a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
    if (v < 0) return -1; // clockwise
    if (v > 0) return +1; // counter-clockwise
    return 0;
}

bool cw(pt a, pt b, pt c, bool include_collinear)
{
    int o = orientation(a, b, c);
    return o < 0 || (include_collinear && o == 0);
}
bool collinear(pt a, pt b, pt c)
{
    return orientation(a, b, c) == 0;
}

void convex_hull(vector<pt>& a, bool include_collinear = false)
{
    pt p0 = *min_element(a.begin(), a.end(), [](pt a, pt b)
    {
        return make_pair(a.y, a.x) < make_pair(b.y, b.x);
    });
    sort(a.begin(), a.end(), [&p0](const pt& a, const pt& b)
    {
        int o = orientation(p0, a, b);
        if (o == 0)
            return (p0.x-a.x)*(p0.x-a.x) + (p0.y-a.y)*(p0.y-a.y)
                   < (p0.x-b.x)*(p0.x-b.x) + (p0.y-b.y)*(p0.y-b.y);
        return o < 0;
    });
    if (include_collinear)
    {
        int i = (int)a.size()-1;
        while (i >= 0 && collinear(p0, a[i], a.back())) i--;
        reverse(a.begin()+i+1, a.end());
    }

    vector<pt> st;
    for (int i = 0; i < (int)a.size(); i++)
    {
        while (st.size() > 1 && !cw(st[st.size()-2], st.back(), a[i], include_collinear))
            st.pop_back();
        st.push_back(a[i]);
    }

    if (include_collinear == false && st.size() == 2 && st[0] == st[1])
        st.pop_back();

    a = st;
}
int main()
{
    fin>>n;
    for (i=1; i<=n; i++)
    {
        pt aux;
        fin>>aux.x>>aux.y;
        a.push_back(aux);
    }
    convex_hull(a);
    fout<<a.size()<<'\n';
    reverse(a.begin()+1,a.end());
    for (auto it : a)
    {
        fout<<it.x<<' '<<it.y<<'\n';
    }
    return 0;
}