namespace split {
    vector<Vertex> poly;
    vector<Point> polyp;
    vector<int> helper;
    vector<int> used;

    struct Edge
    {
        int from, to;
        int next;
        bool isBad;
    };
    vector<Edge> edges;
    vector<vector<int>> g;

    enum class VertexType
    {
        Start,
        End,
        Split,
        Merge,
        Regular,
    };

    bool isInside(Point p, Point p1, Point p2)
    {
        assert(p1.y > p2.y);
        return p2.y <= p.y && p.y <= p1.y;
    }

    bool isOnLeft(Point p, Point p1, Point p2)
    {
        assert(p1.y > p2.y);
        return (p2 - p1) % (p - p1) < 0;
    }

    int prevEdge(int v)
    {
        return v ? v - 1 : polyp.size() - 1;
    }

    int nextEdge(int v)
    {
        return v;
    }

    Point prevVert(int e)
    {
        return polyp[e];
    }

    Point nextVert(int e)
    {
        return e + 1 < polyp.size() ? polyp[e + 1] : polyp[0];
    }

    VertexType getType(int id) {
        auto const& v = poly[id].p;
        auto const& next = nextVert(nextEdge(id));
        auto const& prev = prevVert(prevEdge(id));

        auto product = (next - v) % (prev - v);

        if (v.y > next.y && v.y > prev.y) {
            if (product > 0)
                return VertexType::Start;
            else if (product < 0)
                return VertexType::Split;
            else
                assert(false);
        }
        else if (v.y < next.y && v.y < prev.y) {
            if (product > 0)
                return VertexType::End;
            else if (product < 0)
                return VertexType::Merge;
            else
                assert(false);
        }
        else {
            if (prev.y != v.y && v.y != next.y)
                return VertexType::Regular;
            else if (product < 0)
                return VertexType::Regular;
            else if (v.y == max(prev.y, next.y))
                return VertexType::Start;
            else if (v.y == min(prev.y, next.y))
                return VertexType::End;
            else
                assert(false);
        }
    }

    struct VertexWrapper
    {
        int v;
    };

    struct EdgeComparator {
        bool operator()(int e1, int e2) {
            auto pe1 = prevVert(e1);
            auto ne1 = nextVert(e1);
            auto pe2 = prevVert(e2);
            auto ne2 = nextVert(e2);

            if (isInside(pe1, pe2, ne2))
                return isOnLeft(pe1, pe2, ne2);
            else if (isInside(ne1, pe2, ne2))
                return isOnLeft(ne1, pe2, ne2);
            else if (isInside(pe2, pe1, ne1))
                return !isOnLeft(pe2, pe1, ne1);
            else if (isInside(ne2, pe1, ne1))
                return !isOnLeft(ne2, pe1, ne1);
            else {

                assert(false);
            }
//            return isOnLeft(prevVert(e1), prevVert(e2), nextVert(e2)) || isOnLeft(nextVert(e1), prevVert(e2), nextVert(e2));
        }

        bool operator()(int e, VertexWrapper v)
        {
            return !isOnLeft(polyp[v.v], prevVert(e), nextVert(e));
        }

        using is_transparent = true_type;
    };

    set<int, EdgeComparator> status;

    void addEdge(int from, int to, bool isBad)
    {
        int num = edges.size();
        edges.push_back({from, to, -1, isBad});
        g[from].push_back(num);
    }

    void addEdge(int a, int b)
    {
        cerr << endl << endl;
        cerr << "!@#$ EDGE " << a << ' ' << b << endl;
        cerr << endl << endl;
        cerr << endl << endl;

        addEdge(a, b, false);
        addEdge(b, a, false);
    }

    int getId(Point p)
    {
        for (int i = 0; i < polyp.size(); i++)
            if (polyp[i] == p)
                return i;
        assert(false);
    }

    void printStatus()
    {
        cerr << "STATUS: ";
        for (int e : status) {
            cerr << "(" << e << " : " << getId(prevVert(e)) << ", " << getId(nextVert(e)) << ")" << ' ';
        }
        cerr << endl;
    }

    void addToStatus(int e, int v)
    {
        if (prevVert(e).y == nextVert(e).y)
            return;
        cerr << "for " << v  << " adding (" << getId(prevVert(e)) << ", " << getId(nextVert(e)) << ")" << endl;

        helper[e] = v;

        cerr << "Before adding:";
        printStatus();
        status.insert(e);
        cerr << "After adding:";
        printStatus();
    }

    void removeFromStatus(int e, int v)
    {
        if (prevVert(e).y == nextVert(e).y)
            return;
        if (getType(helper[e]) == VertexType::Merge)
            addEdge(v, helper[e]);

        status.erase(status.find(e));
    }

    int findLeftEdge(int v)
    {
        printStatus();

        auto iter = status.lower_bound(VertexWrapper{v});
//        assert(iter != status.end());
        assert(iter != status.begin());
        iter--;

        cerr << "for " << v << " found " << *iter << endl;

        return *iter;
    }

    void updateHelper(int v, bool forceEdge=false)
    {
        int leftEdge = findLeftEdge(v);
        if (forceEdge || getType(helper[leftEdge]) == VertexType::Merge)
            addEdge(v, helper[leftEdge]);
        helper[leftEdge] = v;
    }

    void handleStart(int v)
    {
        addToStatus(nextEdge(v), v);
    }

    void handleEnd(int v)
    {
        removeFromStatus(prevEdge(v), v);
    }

    void handleSplit(int v) {
        updateHelper(v, true);
        addToStatus(nextEdge(v), v);
    }

    void handleMerge(int v) {
        removeFromStatus(prevEdge(v), v);
        updateHelper(v);
    }

    void handleRegular(int v) {
        if (prevVert(prevEdge(v)).y > nextVert(nextEdge(v)).y) {
            cerr << "!here" << endl;
            removeFromStatus(prevEdge(v), v);
            addToStatus(nextEdge(v), v);
        }
        else {
            cerr << "@here" << endl;
            updateHelper(v);
            cerr << "status after @here:" << endl;
            printStatus();
        }
    }

    void dfs(int e, vector<Vertex>& vs)
    {
        used[e] = true;
        vs.push_back(poly[edges[e].from]);

        int next_e = edges[e ^ 1].next;
        if (!used[next_e])
            dfs(next_e, vs);
    }

    bool testYPoly(vector<Vertex> const& vs) {
        for (int i = 0; i < vs.size(); i++) {
            Point prev = i ? vs[i - 1].p : vs.back().p;
            Point next = i + 1 < vs.size() ? vs[i + 1].p : vs[0].p;
            Point curr = vs[i].p;

            auto product = (next - curr) % (prev - curr);

            if ((curr.y > next.y && curr.y > prev.y || curr.y < next.y && curr.y < prev.y) && product < 0) {
                cerr << endl << endl << endl << endl;
                cerr << "!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!" << endl;
                cerr << prev.x << ' ' << prev.y << " ; " << curr.x << ' ' << curr.y << " ; " << next.x << ' ' << next.y << endl;
                for (int i = 0; i < vs.size(); i++)
                    cerr << vs[i].p.x << ' ' << vs[i].p.y << " ; ";
                cerr << endl;

                return false;
            }
        }

        return true;
    }

    bool testSplit(vector<vector<Vertex>> const& split)
    {
        size_t totalTriangles = 0;
        for (auto vs : split) {
            if (!testYPoly(vs))
                return false;
            totalTriangles += vs.size() - 2;
        }

        cout << "all polys are y-monotonos" << endl;

        return totalTriangles == poly.size() - 2;
    }

    vector<vector<Vertex>> splitYPoly(vector<Vertex> _poly) {
        split::poly.clear();
        split::polyp.clear();
        split::helper.clear();
        split::used.clear();
        split::status.clear();
        split::edges.clear();
        split::g.clear();

        poly = _poly;
        g.resize(poly.size());

        ofstream output("c.out");
        output << poly.size() << endl;
        for (auto i = 0; i < poly.size(); i++)
            output << poly[i].p.x << ' ' << poly[i].p.y << endl;


        polyp.resize(poly.size());
        for (size_t i = 0; i < poly.size(); i++)
            polyp[i] = poly[i].p;

        helper.resize(_poly.size());

        vector<int> ids(poly.size());
        for (int i = 0; i < ids.size(); i++)
            ids[i] = i;

        sort(ids.begin(), ids.end(), [](int id1, int id2) {
            return poly[id1].p.y > poly[id2].p.y || poly[id1].p.y == poly[id2].p.y && poly[id1].p.x < poly[id2].p.x;
        });


        for (auto id : ids)
            cerr << id << ' ';
        cerr << endl;

        for (auto id : ids) {
            cerr << "processing " << id << endl;
            switch (getType(id)) {
                case VertexType::Start:
                    handleStart(id);
                    break;
                case VertexType::End:
                    handleEnd(id);
                    break;
                case VertexType::Split:
                    handleSplit(id);
                    break;
                case VertexType::Merge:
                    handleMerge(id);
                    break;
                case VertexType::Regular:
                    handleRegular(id);
                    break;
            }
        }

        for (int i = 0; i < polyp.size(); i++) {
            addEdge(i, (i + 1) % polyp.size(), false);
            addEdge((i + 1) % polyp.size(), i, true);
        }

        ofstream out("a.out");
        for (size_t i = 0; i < polyp.size(); i++)
            for (auto e : g[i])
                out << edges[e].from << ' ' << edges[e].to << endl;

        for (int i = 0; i < polyp.size(); i++) {
            sort(g[i].begin(), g[i].end(), [](int e1, int e2) {
                return (polyp[edges[e1].to] - polyp[edges[e1].from]).angle() < (polyp[edges[e2].to] - polyp[edges[e2].from]).angle();
            });

            for (size_t j = 1; j < g[i].size(); j++)
                edges[g[i][j]].next = g[i][j - 1];
            edges[g[i][0]].next = g[i].back();
        }

        used.resize(edges.size());
        vector<vector<Vertex>> result;
        for (int i = 0; i < edges.size(); i++)
            if (!used[i] && !edges[i].isBad) {
                vector<Vertex> current;
                dfs(i, current);
                result.push_back(current);
            }

        ofstream out2("b.out");
        out2 << result.size() << endl;
        for (auto vs : result) {
            out2 << vs.size() << endl;
            for (auto v : vs)
                out2 << v.p.x << ' ' << v.p.y << endl;
        }

        assert(testSplit(result));

        return result;
    }
}