题意分析

本题要求根据给定的星图（包含星星的坐标和亮度）以及星座（包含星星的坐标），计算每个星座在星图中出现的次数，并找出最亮的那一次出现的位置（如果存在）。出现是指星图中的一组星星构成与给定星座相同的形状（可能经过旋转和/或缩放）。一次出现的亮度是所包含星星的亮度之和除以星星数量。输入包含多个星图，每个星图先给出星星数量和星星信息，再给出星座数量和每个星座的信息，以一个空星图（星星数量为0）结束输入。输出要求按指定格式输出星图编号、每个星座的出现次数和最亮出现位置。

解题思路

1. 输入处理：
   • 读取星图中星星的数量n，然后依次读取每个星星的x坐标、y坐标和亮度，存储在数组p中。
   • 读取星座的数量m，对于每个星座，先读取星星数量k和星座名称name，再依次读取每个星星的x坐标和y坐标，存储在数组l中。
2. 判断星座出现次数和最亮位置：
   • 对于每个星座，通过两层循环遍历星图中的星星对（i和j），作为星座的起始两个星星。
   • 根据给定的get_move函数，计算星座中其他星星经过旋转和缩放后在星图中的对应位置。
   • 检查计算出的位置在星图中是否存在对应的星星，如果都存在，则认为找到了一次星座的出现，记录下这次出现的星星集合和亮度总和。
   • 重复上述过程，统计星座出现的总次数，并记录最亮的一次出现的星星集合。
3. 计算星座自身的出现情况（用于去重）：
   • 对于每个星座，通过两层循环遍历星座自身的星星对（i和j），作为起始两个星星。
   • 同样使用get_move函数计算其他星星的位置，检查是否都在星座自身中存在，统计这种情况的次数，用于对星图中星座出现次数进行去重。
4. 输出结果：
   • 输出星图编号，格式为“Map #n”。
   • 对于每个星座，先输出一个空行，然后输出星座名称和在星图中出现的次数，格式为“星座名称 occurs 次数 time(s) in the map.”。
   • 如果星座出现次数大于0，输出最亮的那一次出现的位置，按照x坐标升序、x坐标相同则按y坐标升序的顺序输出星星的坐标，格式为“Brightest occurrence: (x1,y1) (x2,y2)...”。
   • 输出一行由5个破折号组成的线（“-----”）分隔不同星图的输出。

复杂度分析

1. 时间复杂度：
   • 输入部分：读取星图和星座信息的时间复杂度为$O(n + m \times k)$，其中n是星图中星星数量，m是星座数量，k是每个星座的星星数量。
   • 判断星座出现次数和最亮位置部分：两层循环遍历星图星星对，对于每个星星对，内部循环计算星座其他星星位置并检查是否存在，时间复杂度为$O(n^2 \times k \times n)$，即$O(n^3 \times k)$。
   • 计算星座自身出现情况部分：两层循环遍历星座自身星星对，对于每个星星对，内部循环计算星座其他星星位置并检查是否存在，时间复杂度为$O(k^2 \times k \times k)$，即$O(k^4)$。
   • 总体时间复杂度为$O(n + m \times k + n^3 \times k + m \times k^4)$。
2. 空间复杂度：
   • 存储星图星星信息的数组p，空间复杂度为$O(n)$。
   • 存储星座星星信息的数组l，空间复杂度为$O(k)$（对于每个星座），总体空间复杂度为$O(m \times k)$。
   • 存储最亮出现星星集合的数组as，空间复杂度为$O(k)$。
   • 其他辅助数组和变量占用的空间为常数级。
   • 总体空间复杂度为$O(n + m \times k)$。

代码实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<algorithm>
#define max_n 1000
#define inf 0x7ffffff
using namespace std;
const double eps = 1e-12;
int flag, ans;

struct P {
    double x, y;
    double light;
};

P p[max_n], l[max_n], as[max_n];
int n, m, k;

// 计算两点之间的距离
double dis(P a, P b) {
    double c = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
    return sqrt(c);
}

// 根据角度和缩放因子计算移动后的点
P get_move(P a, P b, double angle, double s) {
    P c;
    b.x -= a.x;
    b.y -= a.y;
    c.x = cos(angle) * b.x * s - sin(angle) * b.y * s + a.x;
    c.y = cos(angle) * b.y * s + sin(angle) * b.x * s + a.y;
    return c;
}

double mxn;
// 比较函数，用于按x坐标升序，x坐标相同则按y坐标升序排序
bool cp(P a, P b) {
    if (a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}

// 判断两个点是否相等
bool equ(P a, P b) {
    if (fabs(a.x - b.x) < eps && fabs(a.y - b.y) < eps)
        return 1;
    return 0;
}

P kk[max_n];
P cmp[max_n];

// 计算星座在星图中出现的次数和最亮出现的位置
void solve() {
    mxn = -inf;
    int lkk = 0;
    ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j)
                continue;
            double angle, s;
            double sum = 0;
            cmp[0] = p[i];
            kk[0] = p[i];
            cmp[1] = p[j];
            kk[1] = p[j];
            sum += p[i].light;
            sum += p[j].light;
            int a;
            lkk = 2;
            for (a = 2; a < k; a++) {
                angle = atan2(l[a].y - l[0].y, l[a].x - l[0].x) - atan2(l[1].y - l[0].y, l[1].x - l[0].x);
                s = dis(l[a], l[0]) / dis(l[1], l[0]);
                cmp[a] = get_move(p[i], p[j], angle, s);
                int fg = 0;
                for (int ii = 0; ii < n; ii++) {
                    if (equ(p[ii], cmp[a])) {
                        sum += p[ii].light;
                        kk[lkk++] = p[ii];
                        fg = 1;
                        break;
                    }
                }
                if (!fg)
                    break;
            }
            if (a == k) {
                ans++;
                if (sum > mxn) {
                    mxn = sum;
                    for (int llp = 0; llp < k; llp++) {
                        as[llp] = kk[llp];
                    }
                }
            }
        }
    }
}

// 计算星座自身的出现情况（用于去重）
int jisuan() {
    int bns = 0;
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            if (i == j)
                continue;
            double angle, s;
            int a;
            int lkk = 2;
            cmp[0] = l[i];
            cmp[1] = l[j];
            for (a = 2; a < k; a++) {
                angle = atan2(l[a].y - l[0].y, l[a].x - l[0].x) - atan2(l[1].y - l[0].y, l[1].x - l[0].x);
                s = dis(l[a], l[0]) / dis(l[1], l[0]);
                cmp[a] = get_move(l[i], l[j], angle, s);
                int fg = 0;
                for (int ii = 0; ii < k; ii++) {
                    if (equ(l[ii], cmp[a])) {
                        fg = 1;
                        break;
                    }
                }
                if (!fg)
                    break;
            }
            if (a == k) {
                bns++;
            }
        }
    }
    return bns;
}

char name[1000];

int main() {
    int step = 1;
    while (~scanf("%d", &n) && n) {
        double kkk = -1;
        int mink;
        printf("Map #%d\n", step++);
        for (int i = 0; i < n; i++) {
            scanf("%lf%lf%lf", &p[i].x, &p[i].y, &p[i].light);
            if (kkk < p[i].light) {
                kkk = p[i].light;
                mink = i;
            }
        }
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            flag = 0;
            ans = 0;
            scanf("%d%s", &k, name);
            for (int i = 0; i < k; i++)
                scanf("%lf%lf", &l[i].x, &l[i].y);
            if (k == 1) {
                printf("\n");
                printf("%s occurs %d time(s) in the map.\n", name, n);
                printf("Brightest occurrence:");
                printf(" (%.0lf,%.0lf)", p[mink].x, p[mink].y);
                printf("\n");
                continue;
            }
            solve();
            int lkj = jisuan();
            printf("\n");
            if (lkj != 0)
                ans = ans / lkj;
            printf("%s occurs %d time(s) in the map.\n", name, ans);
            if (ans > 0) {
                printf("Brightest occurrence:");
                sort(as, as + k, cp);
                for (int j = 0; j < k; j++) {
                    printf(" (%.0lf,%.0lf)", as[j].x, as[j].y);
                }
                printf("\n");
            }
        }
        printf("-----\n");
    }
    return 0;
}