Cod sursa(job #2417326)

Utilizator GoogalAbabei Daniel Googal Data 29 aprilie 2019 15:32:30
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cmath>
#define err 1e-12

using namespace std;

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

const int NMAX = 120000;

struct Point
{
    double x;
    double y;

    bool operator<(Point other) const
    {
        if(err < abs(x - other.x))
            return (x < other.x);
        else
            return (y < other.y);
    }
};

int n, minn = 1;
int st[1 + NMAX], last;
Point v[1 + NMAX];

double det(Point a, Point b, Point c)
{
    double plus = a.x * b.y + b.x * c.y + a.y * c.x;
    double minus = c.x * b.y + a.y * b.x + a.x * c.y;
    return (plus - minus);
}

bool cmp(Point b, Point c)
{
    Point a = v[1];
    return ((det(a, b, c)) < 0);
}

int main()
{
    in >> n;

    for(int i = 1; i <= n; i++)
    {
        in >> v[i].x >> v[i].y;
        if(v[i] < v[minn])
            minn = i;
    }

    swap(v[1], v[minn]);
    sort(v + 2, v + n + 1, cmp);

    st[1] = 1;
    st[2] = 2;
    last = 2;

    for(int i = 3; i <= n; i++)
    {
        while(last >= 2 && det(v[st[last - 1]], v[st[last]], v[i]) > 0)
            last--;
        st[++last] = i;
    }

    out << last << '\n';
    out << setprecision(6) << fixed;

    for(int i = last; i >= 1; i--)
    {
        out << v[st[i]].x << ' ' << v[st[i]].y << '\n';
    }

    in.close();
    out.close();

    return 0;
}