题目链接：传送门

Description

题目就不放了...

Input

输入的第一行是2个用空格隔开的整数，n、m，分别表示了地图的长和宽。 第二行是3个用空格隔开的整数，s、d、r，依次表示炮塔的个数、单次攻击伤害以及攻击范围。 接下来s行，每行是2个用空格隔开的整数x、y，描述了一个炮塔的位置。当然，蚂蚁窝的洞口以及蛋糕所在的位置上一定没有炮塔。 最后一行是一个正整数t，表示我们模拟游戏的前t秒钟。

Output

如果在第t秒或之前蚂蚁抢到了蛋糕，输出一行“Game over after x seconds”，其中x为游戏结束的时间，否则输出“The game is going on”。 如果游戏在t秒或之前结束，输出游戏结束时所有蚂蚁的信息，否则输出t秒后所有蚂蚁的信息。格式如下： 第一行是1个整数s，表示此时活着的蚂蚁的总数。 接下来s行，每行5个整数，依次表示一只蚂蚁的年龄（单位为秒）、等级、当前血量，以及在地图上的位置（a，b）。输出按蚂蚁的年龄递减排序。

Sample Input

3 5 1 1 2 2 2 5

Sample Output

The game is going on 5 5 1 3 1 4 4 1 3 0 4 3 1 3 0 3 2 1 3 0 2 1 1 4 0 1

Solution

从题目的长度来看就可以看出这道题有多么工业 这道题就是一个特别考验耐心的大模拟再加一点计算几何 6.22K，300行的代码再一次次刷新了我对工业的认识 几个需要注意的地方：

  1. 判断方向当信息素最多的点有多个时，是在这几个点中从向东开始顺时针找最靠前的，而不是在所有方向中去找能走的方向（我本来是这么理解的，后来感觉如果有多个信息素最多的点就直接在所有方向中找能走的，和信息素无关，后来调好久没调出来，改成原来的代码就A了。。。）
  2. (0,0)位置如果有蚂蚁就不能新出生
  3. 存图的数组和存信息素的数组不能弄到一起
  4. 计算几何的部分还不是特别理解，待会儿还要再仔细学一下

Code(第一个6K的代码)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int Maxn = 22;
struct Antt
{
    int x, y, alive, age, blood, level, target, blood_init;
    int prex, prey;
}Ant[10];

struct Tower
{
    int x, y;
}Tower[Maxn];

int N, M, S, D, R, T;
int Ant_sum;
int Map[10][10], dr[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int Val[10][10];
int Cake;
/*    3
      ^
      |
 2<---#---> 0
      |
      v
      1
*/

struct point {int x, y; };
struct line {point a, b; } l;
point sub (point a, point b) {point t; t.x = a.x - b.x; t.y = a.y - b.y; return t; }
inline int cmul (point a, point b) {return a.x * b.y - a.y * b.x;}
inline int turn (point a, point b, point c) {return cmul(sub(b, a), sub(c, a)); }
inline int sqr (int x) { return x * x; }
double caldis (int x1, int y1, int x2, int y2) {return sqrt(sqr(x1 - x2) + sqr(y1 - y2)); }
inline int cdis (int x, int y) {return sqr(Tower[x].x - Ant[y].x) + sqr(Tower[x].y - Ant[y].y);}
double getdis (int x, int y) {return sqrt(cdis(x, y)); }

double Pow (double a, int b)
{
    double Ans = 1.0;
    for (int i = 1; i <= b; ++i)
        Ans *= a;
    return Ans;
}

inline void Born()
{
    if (Map[0][0] == 1) return ;
    for (int i = 1; i <= 6; ++i)
        if (!Ant[i].alive)
        {
            Ant[i].alive = 1;
            Ant[i].x = 0, Ant[i].y = 0;
            Map[Ant[i].x][Ant[i].y] = 1;
            Ant[i].prex = 0, Ant[i].prey = 0;
            Ant_sum++;
            Ant[i].level = (Ant_sum - 1) / 6 + 1;
            Ant[i].age = 0;
            Ant[i].blood = (int)(4.0 * Pow(1.1, Ant[i].level));
            Ant[i].blood_init = Ant[i].blood;
            Ant[i].target = 0;
            return ;
        }
}

inline void Mark()
{
    for (int i = 1; i <= 6; ++i)
    {
        if (!Ant[i].alive) continue;
        if (!Ant[i].target) Val[Ant[i].x][Ant[i].y] += 2;
        else Val[Ant[i].x][Ant[i].y] += 5;
    }
}

inline int cmp (Antt a, Antt b)
{
    return a.age > b.age;
}

inline int pre (int x)
{
    if (!x) return 3;
    return x - 1;
}

inline void Move()
{
    sort(Ant + 1, Ant + 7, cmp);
    for (int i = 1; i <= 6; ++i)
    {
        if (!Ant[i].alive) continue;
        int dir = 100;
        for (int d = 0; d < 4; ++d)
        {
            int dx = Ant[i].x + dr[d][0];
            int dy = Ant[i].y + dr[d][1];
            if (dx < 0 || dx > N || dy < 0 || dy > M) continue;
            if (Map[dx][dy] != 0 || (dx == Ant[i].prex && dy == Ant[i].prey)) continue;
            if (dir == 100) {dir = d; continue;}
            if (Val[Ant[i].x + dr[dir][0]][Ant[i].y + dr[dir][1]] >= Val[dx][dy]) continue;
            dir = d;
        }
        if (dir == 100)
        {
            Ant[i].prex = Ant[i].x;
            Ant[i].prey = Ant[i].y;
            continue;
        }
        /*
        if (fl)
            {
                dir = 3;
                int flag = 0;
                while (1)
                {
                    dir = (dir + 1) % 4;
                    int dx = Ant[i].x + dr[dir][0];
                    int dy = Ant[i].y + dr[dir][1];
                    if (dx < 0 || dx > N || dy < 0 || dy > M) continue;
                    if (Map[dx][dy] != 0 || (dx == Ant[i].prex && dy == Ant[i].prey)) continue;
                    break;
                }
            }
        */

        /*
        if (dir == 100)
        {
            Ant[i].prex = Ant[i].x;
            Ant[i].prey = Ant[i].y;
            continue;
        }
        */
        if (!((Ant[i].age + 1) % 5))
        {
            while (1)
            {
                dir = pre(dir);
                int dx = Ant[i].x + dr[dir][0];
                int dy = Ant[i].y + dr[dir][1];
                if (dx < 0 || dx > N || dy < 0 || dy > M) continue;
                if (Map[dx][dy] != 0 || (dx == Ant[i].prex && dy == Ant[i].prey)) continue;
                break;
            }
        }
        Ant[i].prex = Ant[i].x;
        Ant[i].prey = Ant[i].y;
        Map[Ant[i].prex][Ant[i].prey] = 0;
        Ant[i].x += dr[dir][0];
        Ant[i].y += dr[dir][1];
        Map[Ant[i].x][Ant[i].y] = 1;
    }
}

inline void Check_before()
{
    for (int i = 1; i <= 6; ++i)
    {
        if (!Ant[i].alive) continue;
        if (Ant[i].x == N && Ant[i].y == M && !Cake)
        {
            Cake = 1;
            Ant[i].target = 1;
            Ant[i].blood = min(Ant[i].blood + (int)(Ant[i].blood_init / 2), Ant[i].blood_init);
        }
    }
}

inline int cross(int x,int y)
{
    double d = caldis(l.a.x, l.a.y, l.b.x, l.b.y);
    if(x == l.a.x && y == l.a.y || x == l.b.x && y == l.b.y) return 1;
    int x1 = min(l.a.x, l.b.x), x2 = max(l.a.x, l.b.x);
    int y1 = min(l.a.y, l.b.y), y2 = max(l.a.y, l.b.y);
    if(x < x1 || x > x2 | y < y1 || y > y2)return 0;
    point p;
    p.x = x;p.y = y;
    if(fabs(turn(l.a, l.b, p)) / d <= 0.5)return 1;
    return 0;
}

inline void Attack(int now)
{
    sort(Ant + 1, Ant + 7, cmp);
    int pos = 0, Dis = 0x3f3f3f3f;
    for (int i = 1; i <= 6; ++i)
    {
        if (!Ant[i].alive) continue;
        int dis = cdis(now, i);
        if (dis <= R * R)
        {
            if (Ant[i].target) pos = i;
            else if (!Ant[pos].target && dis < Dis)
                Dis = dis, pos = i;
        }
    }
    if (!pos) return ;
    l.a.x = Tower[now].x; l.a.y = Tower[now].y;
    l.b.x = Ant[pos].x; l.b.y = Ant[pos].y;
    for (int i = 1; i <= 6; ++i)
    {
        if (!Ant[i].alive) continue;
        if (cross(Ant[i].x, Ant[i].y))
            Ant[i].blood -= D;
    }
}

inline void Check_after()
{
    for (int i = 1; i <= 6; ++i)
    {
        if (!Ant[i].alive) continue;
        if (Ant[i].blood < 0)
        {
            if (Ant[i].target) Ant[i].target = 0, Cake = 0;
            Map[Ant[i].x][Ant[i].y] = 0;
            Ant[i].x = 0, Ant[i].y = 0, Ant[i].alive = 0, Ant[i].blood = 0, Ant[i].age = 0, Ant[i].level = 0;
            Ant[i].prex = 0, Ant[i].prey = 0, Ant[i].blood_init = 0;
        }
    }
}

inline void Print()
{
    sort(Ant + 1, Ant + 7, cmp);
    int Cnt = 0;
    for (int i = 1; i <= 6; ++i)
        if (Ant[i].alive) ++Cnt;
    cout<<Cnt<<endl;
    for (int i = 1; i <= 6; ++i)
    {
        if (!Ant[i].alive) continue;
        printf("%d %d %d %d %d\n", Ant[i].age, Ant[i].level, Ant[i].blood, Ant[i].x, Ant[i].y);
    }
}

inline void Check(int x)
{
    for (int i = 1; i <= 6; ++i)
    {
        if (!Ant[i].alive) continue;
        if (Ant[i].target && !Ant[i].x && !Ant[i].y)
        {
            printf("Game over after %d seconds\n", x);
            Print();
            exit(0);
        }
    }
}

inline void Last()
{
    for (int i = 0; i <= 8; ++i)
        for (int j = 0; j <= 8; ++j)
            if (Val[i][j] > 0) Val[i][j] --;
    for (int i = 1; i <= 6; ++i)
        if (Ant[i].alive)
            Ant[i].age++;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    scanf("%d%d%d%d%d", &N, &M, &S, &D, &R);
    for (int i = 1; i <= S; ++i)
        scanf("%d %d", &Tower[i].x, &Tower[i].y), Map[Tower[i].x][Tower[i].y] = -1;
    scanf("%d", &T);
    for (int i = 1; i <= T; ++i)
    {
        Born();
        Mark();
        Move();
        Check_before();
        for (int k = 1; k <= S; ++k) Attack(k);
        Check_after();
        Check(i);
        Last();
    }
    /*
    for (int i = 0; i <= N; ++i)
    {
        for (int j = 0 ; j <= M; ++j)
            printf("%5d", Map[i][j]);
        cout<<endl;
    }
    */
    puts("The game is going on");
    Print();
    return 0;
}