Cod sursa(job #3225713)

Utilizator stefan05Vasilache Stefan stefan05 Data 18 aprilie 2024 15:48:07
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <climits>

#define NMAX 120005
#define Point pair<double, double>
#define x first
#define y second
#define EPS 0.00001
#define INF INT_MAX
#define INF INT_MAX

using namespace std;

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

int n;
vector<Point> pct;
int i;

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

int main()
{
    fin >>n;
    pct.resize(n);
    Point p0; int ind = 0;
    p0 = {INF, INF};
    for (i = 0; i < n; ++i)
    {
        fin >>pct[i].x>>pct[i].y;
        if (p0.y > pct[i].y)
            p0 = pct[i], ind = i;
        else
            if (p0.y == pct[i].y && p0.x > pct[i].x)
                p0 = pct[i], ind = i;
    }

    swap(pct[0], pct[ind]);
    sort(pct.begin()+1, pct.end(), comp);

    vector<Point> st;
    st.push_back(pct[0]);
    st.push_back(pct[1]);
    for (i = 2; 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]);
    }

    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)
{
    int o = orientation(pct[0], a, b);

    if (o == 0)
        return dist(pct[0], a) < dist(pct[0], b);

    return (o < 0);
}

double dist(Point a, Point b)
{
    return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
}

int orientation(Point a, Point b, Point c)
{
    double o = (b.y-a.y)*(c.x-b.x) - (c.y-b.y)*(b.x-a.x);
    if (abs(o) <= EPS)
        return 0;

    return (o < 0? -1: 1);
}