1 /*
2 11:01 -11:21
3 12:19 -12:54
4 16:10 -17:03
5 6:43 - 8:26
6 直接x+0.5取最近小數，負數會出問題
7 在用C風格不是很煩的前提下，盡量少用stl，更快*/
8 #include<cmath>
9 #include<cstdio>
10 #include<algorithm>
11 using namespace std;
12
13 struct Star {
14 int x, y, b;
15 bool operator<(const Star & s)const {
16 return x < s.x || x == s.x && y < s.y;
17 }
18 };
19 Star Map[1024], Cons[1024], best[1024];
20 int brightness, Msize, Csize, bsize;
21 char name[128];
22
23 int round(double x){
24 return x < 0 ? x - 0.5 : x + 0.5;
25 }
26
27 int calc(Star Map [], Star Cons[], int Msize, int Csize) {
28 if (Csize == 1) {
29 for (int i = 0; i < Msize; i++)
30 if (Map[i].b > brightness) {
31 brightness = Map[i].b;
32 bsize = 1;
33 best[0] = Map[i];
34 }
35 return Msize;
36 }
37 int cnt = 0;
38 for (int i = 0; i < Msize; i++)
39 for (int j = 0; j < Msize; j++)
40 if (i != j) {
41 Star tem[1024];
42 int tsize = 0;
43 double a = Map[j].x - Map[i].x;
44 double b = Map[j].y - Map[i].y;
45 double c = Cons[1].x - Cons[0].x;
46 double d = Cons[1].y - Cons[0].y;
47 double sinx, cosx;
48 sinx = (c * b - d * a) / (c*c + d*d);
49 cosx = (a * c + b * d) / (c*c + d*d);
50 tem[tsize++] = Map[i];
51 tem[tsize++] = Map[j];
52 int k;
53 for(k = 2; k < Csize; k++){
54 double x = cosx*(Cons[k].x - Cons[0].x) - sinx * (Cons[k].y - Cons[0].y) + Map[i].x;
55 double y = sinx*(Cons[k].x - Cons[0].x) + cosx * (Cons[k].y - Cons[0].y) + Map[i].y;
56 int ix = round(x);
57 int iy = round(y);
58 if(fabs(x - ix) > 1e-5 || fabs(y - iy) > 1e-5)break;
59 int t;
60 for(t = 0; t < Msize; t++)
61 if(Map[t].x == ix && Map[t].y == iy){
62 tem[tsize++] = Map[t];
63 break;
64 }
65 if(t == Msize)break;
66 }
67 if(k == Csize){
68 cnt++;
69 int sum = 0;
70 for(int i = 0; i < tsize; i++)
71 sum += tem[i].b;
72 if(sum > brightness){
73 brightness = sum;
74 for(int i = 0; i < tsize; i++)
75 best[i] = tem[i];
76 bsize = tsize;
77 }
78 }
79 }
80 return cnt;
81 }
82
83 void solve() {
84 brightness = 0;
85 int ans = calc(Map, Cons, Msize, Csize) / calc(Cons, Cons, Csize, Csize);
86 printf("\n%s occurs %d time(s) in the map.\n", name, ans);
87 if (ans) {
88 sort(best, best + bsize);
89 printf("Brightest occurrence:");
90 for (int i = 0; i < bsize; i++)
91 printf(" (%d,%d)", best[i].x, best[i].y);
92 printf("\n");
93 }
94 }
95
96 int main() {
97 //freopen("in", "r", stdin);
98 int n, cas = 1;
99 while (scanf("%d", &Msize) && Msize) {
100 for (int i = 0; i < Msize; i++)
101 scanf("%d %d %d", &Map[i].x, &Map[i].y, &Map[i].b);
102 printf("Map #%d\n", cas++);
103 for (scanf("%d", &n); n > 0; n--) {
104 scanf("%d %s", &Csize, name);
105 for (int i = 0; i < Csize; i++) {
106 scanf("%d %d", &Cons[i].x, &Cons[i].y);
107 Cons[i].b = 0;
108 }
109 solve();
110 }
111 printf("-----\n");
112 }
113 }
posted on 2009-10-20 20:58
wangzhihao 閱讀(174)
評論(0) 編輯 收藏 引用 所屬分類:
geometry