c47185_b.cpp

#include <iostream>
#include <assert.h>
#include <inttypes.h>
#include <math.h>
#include <vector>
#include <algorithm>


const unsigned int N = 100000;
const unsigned int C = 20;
const int X = 2000000000;

struct Point {
    int x, y;
    Point(int _x, int _y) : x(_x), y(_y) {}
};

struct Multi {
    std::vector<Point> v;
    unsigned int idx;
};

bool operator< (const Multi &a, const Multi &b)
{
    Point p = a.v[0];
    unsigned int l = b.v.size() - 1;
    double alpha = 0;

    for (unsigned int i = 0; i < l; i++) {
        double dx1 = b.v[i].x - (double) p.x;
        double dy1 = b.v[i].y - (double) p.y;
        double dx2 = b.v[i + 1].x - (double) p.x;
        double dy2 = b.v[i + 1].y - (double) p.y;
        double dx0 = b.v[i + 1].x - (double) b.v[i].x;
        double dy0 = b.v[i + 1].y - (double) b.v[i].y;
        double d21 = dx1 * dx1 + dy1 * dy1;
        double d22 = dx2 * dx2 + dy2 * dy2;
        double d20 = dx0 * dx0 + dy0 * dy0;
        assert (d20 > 0);
        double dz = dx1 * dy2 - dx2 * dy1;
        assert (dz != 0);
        double sa = dz, ca = 0.5 * (d21 + d22 - d20);
        alpha += atan2(sa, ca);
    }

    //printf("alpha = %.16f\n", alpha * 0.5);
    return fabs(alpha) < 3;
}

int main()
{
    unsigned int n = 0;
    std::cin >> n;
    assert (std::cin);
    assert (3 <= n && n <= N);
    std::vector<Multi> ms;
    for (unsigned int i = 0; i < n; i++) {
        unsigned int c = 0;
        std::cin >> c;
        assert (std::cin);
        assert (3 <= c && c <= C);
        Multi mi;
        mi.idx = i;
        mi.v.reserve(c + 1);

        for (unsigned int j = 0; j < c; j++) {
            int x = 0, y = 0;
            std::cin >> x >> y;
            assert (std::cin);
            assert (-X <= x && x <= X);
            assert (-X <= y && y <= X);
            mi.v.push_back(Point(x, y));
        }
        mi.v.push_back(mi.v[0]);
        ms.push_back(mi);
    }

    std::sort(ms.begin(), ms.end());
    std::vector<unsigned int> res(n, 0);
    for (unsigned int i = 0; i < n; i++) {
        res[ms[i].idx] = i;
    }
    for (unsigned int i = 0; i < n; i++)
        std::cout << res[i] << ' ';
    std::cout << std::endl;
    return 0;
}