Cod sursa(job #2719621)

Utilizator beingsebiPopa Sebastian beingsebi Data 10 martie 2021 01:56:43
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.17 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
typedef double ll;
struct point
{
    ll x, y;
    point() { x = y = 0; }
    point(ll _x, ll _y)
    {
        x = _x;
        y = _y;
    }
    friend istream &operator>>(istream &is, point &t)
    {
        is >> t.x >> t.y;
        return is;
    }
    friend ostream &operator<<(ostream &os, const point &t)
    {
        os << t.x << " " << t.y << '\n';
        return os;
    }
    point operator+(const point &other) const
    {
        return point{this->x + other.x, this->y + other.y};
    }
    point &operator+=(const point &other)
    {
        *this = *this + other;
        return *this;
    }
    point operator-(const point &other) const
    {
        return point{this->x - other.x, this->y - other.y};
    }
    point &operator-=(const point &other)
    {
        *this = *this - other;
        return *this;
    }
    ll operator*(const point &other) const
    {
        return (ll)x * other.y - (ll)other.x * y;
    }
    ll compare(const point &a, const point &b) const
    {
        return (a - *this) * (b - *this);
    }
    bool operator<(const point &a) const
    {
        return (make_pair(x, y) < make_pair(a.x, a.y));
    }
};
// #define f cin
// #define g cout
vector<point> v;
int main()
{
    ios_base::sync_with_stdio(false);
    f.tie(nullptr);
    int n;
    f >> n;
    v.resize(n);
    for (point &i : v)
        f >> i;
    sort(v.begin(), v.end());
    vector<point> hull;
    for (int rep = 0; rep < 2; rep++)
    {
        int ax = hull.size();
        for (point c : v)
        {
            while (hull.size() - ax >= 2)
            {
                point a = hull.end()[-2];
                point b = hull.end()[-1];
                if (a.compare(b, c) <= 0)
                    break;
                hull.pop_back();
            }
            hull.push_back(c);
        }
        hull.pop_back();
        reverse(v.begin(), v.end());
    }
    g << hull.size() << '\n';
    reverse(hull.begin(), hull.end());
    for (const auto &i : hull)
        g << i;
    return 0;
}