随笔-21  评论-10  文章-21  trackbacks-0
  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*+ d*d);
 49                 cosx = (a * c + b * d) / (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 阅读(164) 评论(0)  编辑 收藏 引用 所属分类: geometry

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理