https://uva.onlinejudge.org/external/6/681.pdf

uva681_convex_hull.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

template<typename T>
class point
{
public:
    friend istream& operator>>(istream& is, point& p)
    {
        is >> p.m_x >> p.m_y;
        return is;
    }

    bool operator==(const point& rhs) const
    {
        return m_x == rhs.x() && m_y == rhs.y();
    }

    T x() const
    {
        return m_x;
    }

    T y() const
    {
        return m_y;
    }

private:
    T m_x;
    T m_y;
};

template<typename P>
vector<P> generate_convex_vertices(vector<P> vertices)
{
    if (*vertices.begin() == *vertices.rbegin())
    {
        vertices.pop_back();
    }

    swap(vertices[0], *min_element(vertices.begin(), vertices.end(), [](const P& p1, const P& p2)
    {
        return p1.y() < p2.y() || (p1.y() == p2.y() && p1.x() < p2.x());
    }));

    auto cross = [](const P& p0, const P& p1, const P& p2)
    {
        return (p1.x() - p0.x()) * (p2.y() - p0.y()) - (p1.y() - p0.y()) * (p2.x() - p0.x());
    };

    const auto& p0 = vertices[0];
    sort(next(vertices.begin()), vertices.end(), [&p0, &cross](const P& p1, const P& p2)
    {
        auto dist2 = [](const P& p0, const P& p1)
        {
            return (p1.x() - p0.x()) ^ 2 + (p1.y() - p0.y()) ^ 2;
        };

        auto c = cross(p0, p1, p2);
        return c > 0 || (c == 0 && dist2(p0, p1) < dist2(p0, p2));
    });

    vector<P> convex_hull;
    for (const auto& p : vertices)
    {
        while (convex_hull.size() >= 2 && cross(*next(convex_hull.rbegin()), *convex_hull.rbegin(), p) <= 0)
        {
            convex_hull.pop_back();
        }

        convex_hull.push_back(p);
    }
    convex_hull.push_back(convex_hull[0]);

    return convex_hull;
}

void test_case(size_t vertex_count)
{
    using point = point<int>;
    vector<point> vertices(vertex_count);
    for (auto& vertex : vertices)
    {
        cin >> vertex;
    }

    auto convex_vertices = generate_convex_vertices(vertices);
    cout << convex_vertices.size() << endl;
    for (const auto& p : convex_vertices)
    {
        cout << p.x() << " " << p.y() << endl;
    }
}

int main()
{
    size_t case_count = 0;
    cin >> case_count;
    cout << case_count << endl;
    while (case_count--)
    {
        int vertex_count = 0;
        cin >> vertex_count;

        if (vertex_count == -1) // ignore delimiter
        {
            cin >> vertex_count;
        }

        test_case(vertex_count);
        if (case_count)
        {
            cout << -1 << endl;
        }
    }
    return 0;
}