Cod sursa(job #3225677)

Utilizator stefan05Vasilache Stefan stefan05 Data 18 aprilie 2024 14:39:32
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>

#define NMAX 120005
#define Point pair<double, double>
#define x first
#define y second
#define CLOCKWISE 1
#define COL 0
#define COUNTER -1

using namespace std;

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

int n;
Point pct[NMAX];
int i;

bool comp(Point, Point);
int orientation(Point, Point, Point);

int main()
{
    fin >>n;
    for (i = 1; i <= n; ++i)
        fin >>pct[i].x>>pct[i].y;

    swap(pct[1], *min_element(pct+2, pct+n+1));
    sort(pct+2, pct+n+1, comp);

    vector<Point> st;
    st.push_back(pct[1]);
    st.push_back(pct[2]);
    for (i = 3; i <= n; ++i)
    {
        while (st.size() > 2 && orientation(st[st.size()-2], st[st.size()-1], pct[i]) >= 0)
            st.pop_back();
        st.push_back(pct[i]);
    }

    //reverse(st.begin(), st.end());

    fout <<fixed<<setprecision(6)<<st.size()<<'\n';
    for (auto crt: st)
        fout <<crt.x<<' '<<crt.y<<'\n';

    fout.close();
    return 0;
}

bool comp(Point a, Point b)
{
    return orientation(pct[0], a, b) == COUNTER;
}

int orientation(Point a, Point b, Point c)
{
    double aux = (b.y-a.y)*(c.x-b.x) - (c.y-b.y)*(b.x-a.x);
    if (aux == 0)
        return COL;
    return (aux < 0? COUNTER: CLOCKWISE);
}