ZJOI 2008 Antbuster 巨型模拟

还是第一次做这么恶心的，断断续续调了一个星期。

来盘点一下错误：

1）求点到线段距离时利用点积判断，大小于号打反了;

2）没有考虑上一秒的点不能再走回去;

3）所有炮塔同时攻击，即使目标血量为负数;

4）一开始没有注意精度问题;

5）当该蚂蚁不能走时，没有判断是否能拿起蛋糕，并更新其上一步的位置;

6)还有很多......

以后写这种模拟一定要一步一步按题目描述来，不要想着一起进行几个步骤，否则极其容易出错。

乱七八糟的代码：

#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>using namespace std;#define Set(i, j) memset(i, j, sizeof(i))
#define For(i, j, k) for(int i = j;i <= k;i++)
#define Forr(i, j, k) for(int i = j;i >= k;i--)const int N = 25, M = 200010;
const int d[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
const double eps = 1e-12;int n, m, T;
int Map[N][N], val[N][N];
double HP[M];int demage, s, r;bool recake;
int tar, now_t;int cnt, tot;struct Ant{int x, y;int nx, ny;int age, hp, lv;bool cake;bool operator < (const Ant& A) const{if(hp < 0) return 0;return age > A.age || A.hp < 0;}void hurt(){hp -= demage;if(hp < 0)Map[x][y] = 0;}void Move(){int dir = -1, Max = -1e9;val[x][y] += cake ? 5 : 2;For(i,0,3){int u = x + d[i][0], v = y + d[i][1];if(u < 0 || v < 0 || Map[u][v] || (u == nx && v == ny)) continue;if(val[u][v] > Max) Max = val[u][v], dir = i;}if(dir < 0){nx = x, ny = y;if(x == n && y == m && recake) recake = 0, cake = 1, hp = min(int(HP[lv]), hp + int(HP[lv] / 2));return;}if(age % 5 == 0)For(j,1,3){int i = (dir - j + 4) % 4;int u = x + d[i][0], v = y + d[i][1];if(u < 0 || v < 0 || Map[u][v] || (u == nx && v == ny)) continue;dir = i;break;}Map[x][y] = 0;nx = x, ny = y;x += d[dir][0], y += d[dir][1];Map[x][y] = 1;if(x == n && y == m && recake) recake = 0, cake = 1, hp = min(int(HP[lv]), hp + int(HP[lv] / 2));}}A[N];double dist(double x, double y){return sqrt(x * x + y * y);
}struct Vector{int x, y;Vector(int u, int v){x = u, y = v;}Vector operator - (const Vector& V) const{return Vector(x - V.x, y - V.y);}
};typedef Vector Point;int dcmp(double x){return x < -eps ? -1 : (x > eps ? 1 : 0);}
double Cross(const Vector& u, const Vector& v){return 1.0 * u.x * v.y - u.y * v.x;}
double Dot(const Vector& u, const Vector& v){return 1.0 * u.x * v.x + u.y * v.y;}
double Length(const Vector& v){return sqrt(Dot(v, v));}
double Dist_to_Segment(Point P, Point B, Point C){Vector v1 = P - B, v2 = P - C, v3 = C - B;if(dcmp(Dot(v3, v1)) < 0) return Length(v1);if(dcmp(Dot(v3, v2)) > 0) return Length(v2);return fabs(Cross(v3, v1)) / Length(v3);
}struct Dorminator{int x, y;bool inrange(const Ant& C){return dist(C.x - x, C.y - y) < r + eps;}void splash(int to){For(i,1,cnt)if(i == to || Dist_to_Segment(Point(A[i].x, A[i].y), Point(x, y),Point(A[to].x, A[to].y)) < 0.5 + eps)A[i].hurt();}void attack(){if(!recake && inrange(A[tar]))splash(tar);else{double Mind = 1e18;int k = -1;For(i,1,cnt){double dis = dist(A[i].x - x, A[i].y - y);if(dcmp(Mind - dis) > 0) Mind = dis, k = i;}if(Mind < r + eps) splash(k);}}}D[N];void init(){recake = 1;HP[1] = 1.1;For(i,2,T) HP[i] = HP[i-1] * 1.1;For(i,1,T) HP[i] *= 4;For(i,1,s) Map[D[i].x][D[i].y] = 2;For(i,0,m+1) Map[n+1][i] = 3;For(i,0,n+1) Map[i][m+1] = 3;
}void born(){if(Map[0][0] || cnt == 6) return;A[++cnt] = (Ant){0, 0, 0, 0, 1, int(HP[tot / 6 + 1]), tot / 6 + 1, false};Map[0][0] = 1;++tot;
}void attack(){For(i,1,cnt){A[i].Move();if(A[i].cake) tar = i;}For(i,1,s) D[i].attack();if(tar && A[tar].hp < 0) recake = 1, A[tar].cake = 0, tar = 0;
}void info(){printf("%d\n", cnt);For(i,1,cnt) printf("%d %d %d %d %d\n", A[i].age - 1, A[i].lv, A[i].hp, A[i].x, A[i].y);
}void check(){sort(A + 1, A + cnt + 1);while(cnt && A[cnt].hp < 0) --cnt;if(!recake){For(i,1,cnt){if(A[i].cake){if(!A[i].x && !A[i].y){printf("Game over after %d seconds\n", now_t);info();exit(0);}tar = i;break;}}}For(i,1,cnt) A[i].age++;For(i,0,n) For(j,0,m) if(val[i][j]) val[i][j]--;
}int main(){scanf("%d%d", &n, &m); scanf("%d%d%d", &s, &demage, &r); For(i,1,s) scanf("%d%d", &D[i].x, &D[i].y); scanf("%d", &T); init(); for(now_t = 1;now_t <= T;now_t++){ born();attack();check();}printf("The game is going on\n");info();return 0;
}