681

681.cpp

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

using namespace std;

template<typename T>
class Point
{
public:
    T x; //QQ
    T y; //QQ

    Point(T x_coor, T y_coor)
    {
        x = x_coor;
        y = y_coor;
    }

    bool operator < (const Point& point) const
    {
        /*if (this->y < point.y) return true;
        if (this->y > point.y) return false;
        if (this->y == point.y)
        {
            if (this->x < point.x) return true;
            if (this->x > point.x) return false;
            if (this->x == point.x) return false;
        }
        return false;*/

        if (this->x < point.x) return true;
        if (this->x > point.x) return false;
        if (this->x == point.x)
        {
            if (this->y < point.y) return true;
            if (this->y > point.y) return false;
            if (this->x == point.x) return false;
        }
        return false;
    }

    bool operator !=(const Point& point) const
    {
        if (this->x != point.x || this->y != point.y) return true;
        else return false;
    }
};

void input(vector< vector < Point<int> > >& pointss)
{
    int data_nums(0), point_nums(0), x(0), y(0), _1(0);
    cin >> data_nums;
    for (int i = 0; i < data_nums; i++)
    {
        vector < Point<int> > points;
        cin >> point_nums;
        for (int j = 0; j < point_nums; j++)
        {
            cin >> x >> y;
            points.push_back(Point<int>(x, y));
        }
        if (data_nums - i > 1) cin >> _1;
        pointss.push_back(points);
    }
}

void output(vector < vector < Point<int> > >& results)
{
    string o = to_string(results.size()) + "\n";
    //cout << results.size() << endl;

    for (size_t i = 0; i < results.size(); i++)
    {
        o = o + to_string(results.size()) + "\n";
        //cout << results[i].size() + 1 << endl;
        size_t ori_point_index(0);
        for (size_t j = 1; j < results[i].size(); j++)
        {
            int min_y(results[i][0].y);
            if (min_y > results[i][j].y)
            {
                ori_point_index = j;
                min_y = results[i][j].y;
            }
        }

        size_t index = ori_point_index;
        for (size_t j = 0; j < results[i].size(); j++)
        {
            o = o + to_string(results[i][index].x) + " " + to_string(results[i][index].y) + "\n";
            //cout << results[i][index].x << " " << results[i][index].y << endl;
            index = (index + 1) % results[i].size();
        }
        o = o + to_string(results[i][ori_point_index].x) + " " + to_string(results[i][ori_point_index].y) + "\n";
        //cout << results[i][ori_point_index].x << " " << results[i][ori_point_index].y << endl;
        if (results.size() - 1 > i)
            o = o + "-1\n";
            //cout << "-1" << endl;
    }
    cout << o;
}

int cross(Point<int> o, Point<int> a, Point<int> b)
{
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

vector<Point<int>> algorithm_(vector < Point<int> > points)
{
    sort(points.begin(), points.end());
    vector < Point<int> > result;
    for (size_t i = 0; i < points.size(); i++)
    {
        while (1)
        {
            if (result.size() < 2)
            {
                if (result.size() == 0) result.push_back(points[i]);
                if (result.back() != points[i]) result.push_back(points[i]);
                break;
            }
            else if (result.back().y < points[i].y)
            {
                if (cross(result[result.size() - 2], result[result.size() - 1], points[i]) > 0)
                {
                    result.push_back(points[i]);
                    break;
                }
                else
                {
                    result.pop_back();
                }
            }
            else
            {
                result.pop_back();
            }
        }
    }

    size_t init_size = result.size();
    for (int i = points.size() - 2; i >= 0; i--)
    {
        while (1)
        {
            if (result.size() < init_size + 1)
            {
                if (result.back() != points[i]) result.push_back(points[i]);
                break;
            }
            else if (result.back().y > points[i].y)
            {
                if (cross(result[result.size() - 2], result[result.size() - 1], points[i]) > 0)
                {
                    result.push_back(points[i]);
                    break;
                }
                else
                {
                    result.pop_back();
                }
            }
            else
            {
                result.pop_back();
            }
        }
    }

    result.pop_back();

    return result;
}

int main()
{
    vector < vector < Point<int> > > pointss;

    input(pointss);

    vector < vector < Point<int> > > results;
    for (size_t i = 0; i < pointss.size(); i++) results.push_back(algorithm_(pointss[i])/*Andrew_monotone_chain(pointss[i])*/);

    output(results);

    return 0;
}