這個(gè)題目我用的是枚舉。具體做法是，對(duì)于每個(gè)星座，把它的第1個(gè)點(diǎn)放在星圖的第i個(gè)點(diǎn)上，第2個(gè)點(diǎn)放在星圖的第j個(gè)點(diǎn)上（i != j），保持形狀不變，移動(dòng)這個(gè)星座中的其他點(diǎn)，看看這些點(diǎn)是否都和星圖中的點(diǎn)重合。若滿足條件，則找到一個(gè)匹配。如此得到星座c對(duì)星圖的匹配數(shù)a。再得到星座c對(duì)它本身的匹配數(shù)b。那么星座c的出現(xiàn)次數(shù)就是 a / b。對(duì)于只有一個(gè)星星的星座，要特殊考慮一下。至于找出最亮星座，方法很簡單：每次記錄亮度值，發(fā)現(xiàn)更亮的就更新解。
p.s. 我一開始是用STL的complex做的，超時(shí)。后來改成向量做了。
/**//*************************************************************************
Author: WHU_GCC
Created Time: 2000-9-8 19:27:20
File Name: pku1133.cpp
Description:
************************************************************************/
#include <iostream>
#include <cmath>
using namespace std;
#define out(x) (cout << #x << ": " << x << endl)
typedef long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) 
{ for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) { for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }
const int maxn = 1000;
typedef struct star_t
{
int x, y, b;
};
int operator <(const star_t &a, const star_t &b)
{
return a.x < b.x || a.x == b.x && a.y < b.y;
}
int n;
star_t map[maxn];
int cnt_col;
int col_size[50];
char col_name[50][50];
star_t col[50][50];
star_t sol[50];
int bright;
int count(star_t ap[], star_t bp[], int size_a, int size_b)
{
int ret = 0;
if (size_b == 1)
{
for (int i = 0; i < size_a; i++)
if (ap[i].b > bright)
{
bright = ap[i].b;
sol[0] = ap[i];
}
return size_a;
}
int p = bp[1].x - bp[0].x;
int q = bp[1].y - bp[0].y;
for (int i = 0; i < size_a; i++)
for (int j = 0; j < size_a; j++) if (i != j)
{
int flag = 1;
int sum_bright = ap[i].b + ap[j].b;
star_t tmp_sol[50];
int len = 2;
tmp_sol[0] = ap[i];
tmp_sol[1] = ap[j];
for (int k = 2; k < size_b; k++)
{
double c = bp[k].x - bp[0].x;
double d = bp[k].y - bp[0].y;
double a = double(c * p + d * q) / double(p * p + q * q);
double b = double(d * p - c * q) / double(p * p + q * q);
double x = a * (ap[j].x - ap[i].x) - b * (ap[j].y - ap[i].y) + ap[i].x;
double y = a * (ap[j].y - ap[i].y) + b * (ap[j].x - ap[i].x) + ap[i].y;
int ix = rint(x);
int iy = rint(y);
if (abs(x - ix) > 1e-5 || abs(y - iy) > 1e-5)
{
flag = 0;
break;
}
int t;
for (t = 0; t < size_a; t++)
{
if (ix == ap[t].x && iy == ap[t].y)
{
tmp_sol[len++] = ap[t];
sum_bright += ap[t].b;
break;
}
}
if (t == size_a)
flag = 0;
}
if (flag != 0)
{
ret++;
if (sum_bright > bright)
{
bright = sum_bright;
memcpy(sol, tmp_sol, sizeof(sol));
}
}
}
return ret;
}
int solve()
{
for (int i = 0; i < cnt_col; i++)
{
bright = 0;
int p = count(map, col[i], n, col_size[i]);
printf("\n%s occurs %d time(s) in the map.\n", col_name[i], p / count(col[i], col[i], col_size[i], col_size[i]));
if (p > 0)
{
printf("Brightest occurrence:");
sort(sol, sol + col_size[i]);
for (int j = 0; j < col_size[i]; j++)
printf(" (%d,%d)", sol[j].x, sol[j].y);
printf("\n");
}
}
printf("-----\n");
}
int main()
{
int ca = 1;
while (scanf("%d", &n), n != 0)
{
for (int i = 0; i < n; i++)
scanf("%d%d%d", &map[i].x, &map[i].y, &map[i].b);
scanf("%d", &cnt_col);
for (int i = 0; i < cnt_col; i++)
{
scanf("%d%s", &col_size[i], &col_name[i]);
for (int j = 0; j < col_size[i]; j++)
scanf("%d%d", &col[i][j].x, &col[i][j].y);
}
printf("Map #%d\n", ca++);
solve();
}
return 0;
}