On a clear moon-less night, you can see millions of stars glimmering in
the sky. Faced with this overwhelming number, the Greeks started
nearly 2,000 years ago to bring some order to the chaos. They identified
groups of stars, called constellations, and gave them names, mostly
from the Greek mythology, that are still in use today. Examples
are ``Ursa Minor'', ``Pisces'', ``Cancer'', and many others.
Given a sketch of the constellation, it is not easy for the amateur to
actually find the constellation in the sky. Moreover, simple constellations,
such as ``Triangulum'' (triangle,) which consists of only three stars, may
appear several times in the sky. Again, singling out the ``correct''
occurrence is not easy.
Traditionally, maps were printed for just this purpose. But in this
problem, we will see how the computer can help us find constellations
in the sky.
You will be given a star map; for simplicity this will be a collection
of points in the plane, each having a certain brightness associated with it.
Then, given a constellation, also as a set of points in the plane,
you are to determine:
- the number of occurrences of the constellation in the star map, and
- the position of the brightest occurrence, if one exists. (The
rationale behind this is as follows: if a constellation seems to
appear several times in the sky, the brightest one is
most likely to be the real one, since it is the most eye-catching one.)
An occurrence is a subset of stars from the map that forms a (possibly)
arbitrarily rotated and/or scaled copy of the stars in the constellation.
The brightness of an occurrence is the average brightness of the stars
it consists of, i.e. the sum of individual brightnesses divided by the
number of stars in the constellation.
The input file contains the descriptions of several star maps. Each map
starts with a line containing a single integer n, specifying the
number of stars in the map ( 
).
The following n lines contain three integers each, namely the x-
and y-coordinates and the brightness of every star. The larger
the value, the brighter the star shines.
The next line contains a single integer m, the number of constellations
to follow ( 
). Each constellation description starts with a
line containing an integer 
, the number of stars in constellation i,
and a string 
, the name of the constellation. ( will consist of
no more than 40 characters and contain no blanks.) The following
lines then contain the coordinates of the constellation, again as x/y-pairs.
A blank line separates the star map from the next map. The input file
ends with an empty map (having n = 0), which should not be processed.
N.B.: Since all star coordinates are integer numbers, you can easily
rule out any rotated or scaled constellation whose points do not
fall on integer coordinates.
For each star map first output the number of the map (`Map #1',
`Map #2', etc.) on a line of its own.
For each constellation, in the same order as in the input, output first
its name and how many times it occurs in the map on one line, as shown
in the output sample.
If there is at least one occurrence, output the position of the brightest
occurrence by listing the positions of the stars that form the brightest
occurrence. The star positions have to be printed in ascending x-order.
Positions having the same x-coordinates must be sorted
in ascending y-order. If there are several equally bright solutions,
output only one of them. Adhere to the format shown in the sample output.
Output a blank line before each constellation and a line of 5
dashes (`-----') after every star map.
6
1 2 1
2 1 4
2 4 3
3 2 1
4 1 5
4 3 2
2
3 Triangulum
1 1
3 1
2 4
4 Cancer
1 3
4 3
6 1
7 5
0
Map #1
Triangulum occurs 2 time(s) in the map.
Brightest occurrence: (1,2) (4,1) (4,3)
Cancer occurs 0 time(s) in the map.
-----
tricky input:
1
1 1 1
4
1 Point
7 8
2 Line
1 4
3 9
3 Triangulum
1 1
3 1
2 4
4 Cancer
1 3
4 3
6 1
7 5
tricky output:
Map #1
Point occurs 1 time(s) in the map.
Brightest occurrence: (1,1)
Line occurs 0 time(s) in the map.
Triangulum occurs 0 time(s) in the map.
Cancer occurs 0 time(s) in the map.
-----
注意同構，字典順序最小。
#include <stdio.h>
#include <math.h>
#include <map>
#include <set>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
struct Pt {
int x, y, w;
bool operator<(const Pt &a) const {
if(x != a.x)
return x < a.x;
return y < a.y;
}
};
struct St {
int V[(1000>>5)+1];
St() {
memset(V, 0, sizeof(V));
}
bool operator<(const St &a) const {
return memcmp(V, a.V, sizeof(V)) > 0;
}
};
int main() {
int n, m, q, i, j, k;
Pt star[1005];//stars in sky
int cases = 0;
while(scanf("%d", &n) == 1 && n) {
map<int, map<int, int> > R;
for(i = 0; i < n; i++)
scanf("%d %d %d", &star[i].x, &star[i].y, &star[i].w);
sort(star, star+n);
for(i = 0; i < n; i++) {
R[star[i].x][star[i].y] = i;
}
scanf("%d", &q);
char name[205];
int buffer[105], res[105];
Pt con[105];//constellation
printf("Map #%d\n", ++cases);
while(q--) {
scanf("%d %s", &m, &name);
for(i = 0; i < m; i++)
scanf("%d %d", &con[i].x, &con[i].y);
int times = 0, light = 0, slight;
map<St, int> hash;
for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
if(i == j && m != 1) continue;
double theta1 = atan2(star[j].y-star[i].y, star[j].x-star[i].x);
double theta2 = atan2(con[1].y-con[0].y, con[1].x-con[0].x);
double rtheta = theta1 - theta2;
double disp = pow(star[j].x-star[i].x,2)+pow(star[j].y-star[i].y,2);
double disq = pow(con[1].x-con[0].x,2)+pow(con[1].y-con[0].y,2);
double scaling = sqrt(disp/disq);
slight = 0;
//printf("%d %d %d %d\n", star[i].x, star[i].y, star[j].x, star[j].y);
//printf("%lf %lf\n", rtheta, scaling);
for(k = 0; k < m; k++) {
double tx = con[k].x-con[0].x;
double ty = con[k].y-con[0].y;
double rx, ry;
rx = tx*cos(rtheta) - ty*sin(rtheta);
ry = tx*sin(rtheta) + ty*cos(rtheta);
rx *= scaling;
ry *= scaling;
rx += star[i].x;
ry += star[i].y;
int ix, iy;
#define eps 1e-6
ix = (int)floor(rx+eps);
iy = (int)floor(ry+eps);
//printf("%d %d\n", ix, iy);
if(fabs(rx-ix) > eps || fabs(ry-iy) > eps)
break;
map<int, map<int, int> >::iterator xt = R.find(ix);
if(xt == R.end())
break;
map<int, int>::iterator yt = (xt->second).find(iy);
if(yt == (xt->second).end())
break;
slight += star[yt->second].w;
buffer[k] = yt->second;
}
if(k == m) {
if(slight > light)
light = slight;
St val;
for(k = 0; k < m; k++)
val.V[buffer[k]>>5] |= 1<<(buffer[k]&31);
hash[val] = slight;
}
//puts("---");
}
}
puts("");
times = hash.size();
printf("%s occurs %d time(s) in the map.\n", name, times);
if(times) {
int first = 0;
for(map<St, int>::iterator it = hash.begin();
it != hash.end(); it++) {
if(it->second == light) {
for(i = 0, j = 0; i < n; i++) {
if((it->first).V[i>>5]>>(i&31)&1)
res[j++] = i;
}
break;
}
}
printf("Brightest occurrence:");
for(i = 0; i < m; i++)
printf(" (%d,%d)", star[res[i]].x, star[res[i]].y);
puts("");
}
}
puts("-----");
}
return 0;
}
文章定位：
