算法题：Extended Braille

问题描述

The Blind Association for Pretty Calligraphy is annoyed by the lack of emoticons and math symbols in the braille alphabet. Given that the braille alphabet is supported by the Unicode format, it only makes sense to make all Unicode characters supported in braille.

The goal is to extend the braille alphabet to include all Unicode characters. Of course, this will not fit in the standard 2×3 format, so using a bigger box is allowed. Important is that no two braille characters are the same up to translation, i.e., have the same shape. See Figure E.1 for an example. You let a designer make up a large braille alphabet, and your job is to check how many unique shapes there are among the characters.

输入格式

The input consists of:

• One line with an integer n (1≤n≤105), the number of braille characters.
• Then for each of the n braille characters:
  • One line with an integer m (1≤m≤1000), the number of dots.
  • m lines, each with two integers x and y (|x|,|y|≤1000), the coordinates of the dots.

The total number of dots is at most 10^6.

输出格式

Output the number of distinct braille characters up to translation.

样例1

输入

2
2
0 2
1 1
2
0 1
1 0

输出

1

样例2

输入

2
3
-1 0
0 1
1 0
3
-1 0
0 -1
1 0

输出

2

数据范围

解决方案

代码

#include <iostream>
#include <set>

using namespace std;

int main() {

    int n;
    cin >> n;

    set<set<pair<int, int>>> s;
    for (int i = 0; i < n; ++i) {
        int m;
        cin >> m;

        int minx = 1005;
        int miny = 1005;
        static pair<int, int> arr[1005];
        for (int j = 0; j < m; ++j) {
            int x, y;
            cin >> x >> y;
            arr[j].first = x;
            arr[j].second = y;

            if (minx > x) {
                minx = x;
            }
            if (miny > y) {
                miny = y;
            }
        }

        set<pair<int, int>> ss;
        for (int j = 0; j < m; ++j) {
            ss.insert({arr[j].first - minx, arr[j].second - miny});
        }
        s.insert(ss);
    }

    cout << s.size();

    return 0;
}