BZOJ[1033] [ZJOI2008] 杀蚂蚁antbuster

第一道大模拟
  1 #include <cmath>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cstring>
  5 #include <iostream>
  6 #include <algorithm>
  7 # define maxBat 30
  8 # define maxT 200010
  9 using namespace std;
 10 int ot(){cout<<"******"<<endl;}
 11 int O(){exit(0);}
 12 int n,m;
 13 int S,D,R,T,CNT;
 14 struct Battery{
 15     int x,y;
 16 }bat[maxBat];
 17 bool pd[10][10];
 18 void init(){
 19     scanf("%d%d",&n,&m);
 20     scanf("%d%d%d",&S,&D,&R);
 21     int x,y;
 22     for(int i=1;i<=S;i++){
 23         scanf("%d%d",&x,&y); 
 24         bat[i].x=x; bat[i].y=y;
 25         pd[x][y]=1;
 26     }
 27     scanf("%d",&T);
 28 }
 29 double px[maxT];
 30 int mov[5][3];
 31 void beg(){
 32     px[0]=1; int lim=(T-1)/6+1;
 33     for(int i=1;i<=lim;i++) px[i]=px[i-1]*1.1;
 34     mov[0][0]=0 ; mov[0][1]=1 ;
 35     mov[1][0]=1 ; mov[1][1]=0 ;
 36     mov[2][0]=0 ; mov[2][1]=-1 ;
 37     mov[3][0]=-1 ; mov[3][1]=0 ;
 38 }
 39 int mes[10][10],now_tot,now_time;
 40 bool Cake,Ed;
 41 struct Ant{
 42     int age,rank,Hp,x,y,cake,bg,id;
 43     int lx,ly;
 44     void A(){
 45     printf("  id=%d  Hp=%d  pos= <%d,%d>  age= %d  rk= %d  ck= %d  bg= %d\n",id,Hp,x,y,age,rank,cake,bg);
 46 }
 47 }ant[15];
 48 int tail;
 49 void Birth(int tim){
 50     if(pd[0][0]) return;
 51     CNT++;
 52     ant[tail].id=CNT;
 53     ant[tail].rank=(CNT-1)/6+1;
 54     ant[tail].bg=ant[tail].Hp=floor(4.0*px[ ant[tail].rank ]);
 55     ant[tail].x=0; ant[tail].y=0;
 56     ant[tail].lx=0; ant[tail].ly=0;
 57     ant[tail].age=1; ant[tail].cake=0;
 58     tail++; now_tot++;
 59     pd[0][0]=1;
 60 }
 61 void Make_mes(){
 62     for(int k=0;k<tail;k++){
 63         if(ant[k].cake) mes[ant[k].x][ant[k].y]+=5;
 64         else mes[ant[k].x][ant[k].y]+=2;
 65     }
 66 }
 67 bool In(int x,int y){
 68     if(x>=0 && x<=n && y>=0 && y<=m) return 1;
 69     return 0;
 70 }
 71 int Mx_mes(int x,int y,int id){
 72     int x_,y_; int mx=-1,ret=-1;
 73     for(int i=0;i<4;i++){
 74         x_=x+mov[i][0]; y_=y+mov[i][1];
 75         if(!In(x_,y_)) continue;
 76         if(x_==ant[id].lx && y_==ant[id].ly) continue;
 77         if(pd[x_][y_]) continue;
 78         if(mes[x_][y_] > mx) mx=mes[x_][y_],ret=i;
 79     }
 80     return ret;
 81 }
 82 int Spi(int x,int y,int now,int id){
 83     now=((now-1)+4)%4;
 84     int x_,y_; x_=x+mov[now][0]; y_=y+mov[now][1];
 85     while(!In(x_,y_) || pd[x_][y_] || (ant[id].lx==x_ && ant[id].ly==y_)){
 86         now=((now-1)+4)%4; 
 87         x_=x+mov[now][0]; y_=y+mov[now][1];
 88     }
 89     return now;
 90 }
 91 void Mov(){
 92     // cout<<"Mov::"<<endl;
 93     int to,x_,y_;
 94     for(int k=0;k<tail;k++){
 95         to=Mx_mes(ant[k].x,ant[k].y,k);
 96         if(to==-1){
 97             ant[k].lx=ant[k].x; ant[k].ly=ant[k].y;
 98             if(ant[k].x==n && ant[k].y==m && !Cake){
 99                 ant[k].Hp+=ant[k].bg/2;
100                 if(ant[k].Hp>ant[k].bg) ant[k].Hp=ant[k].bg;
101                 Cake=1; ant[k].cake=1;
102             }
103             continue;
104         }
105         if(ant[k].age%5==0) to=Spi(ant[k].x,ant[k].y,to,k);
106         x_=ant[k].x+mov[to][0]; y_=ant[k].y+mov[to][1];
107         pd[ant[k].x][ant[k].y]=0;
108         ant[k].lx=ant[k].x; ant[k].ly=ant[k].y;
109         // printf("  %d:: (%d,%d)-->(%d,%d)\n",ant[k].id,ant[k].x,ant[k].y,x_,y_);
110         ant[k].x=x_; ant[k].y=y_;
111         pd[ant[k].x][ant[k].y]=1;
112         if(x_==n && y_==m && !Cake){
113             ant[k].Hp+=ant[k].bg/2;
114             if(ant[k].Hp>ant[k].bg) ant[k].Hp=ant[k].bg;
115             Cake=1; ant[k].cake=1;
116         }
117     }
118     // cout<<endl;
119 }
120 double Dis(int k,int i){
121     double dis=sqrt((ant[k].x-bat[i].x)*(ant[k].x-bat[i].x) + (ant[k].y-bat[i].y)*(ant[k].y-bat[i].y));
122     return dis;
123 }
124 int Find_a(int i){
125     int aim=-1; double dis,mn=1000000.0;
126     for(int k=0;k<tail;k++){
127         dis=Dis(k,i); 
128         if(dis>(double)R){continue;}
129         if(ant[k].cake) return k;
130         if(mn>dis) mn=dis,aim=k;
131     }
132     return aim;
133 }
134 struct LINE{
135     double k,b;
136     int x,y,x_,y_;
137 };
138 LINE Get_line(double x,double y,double x_,double y_){
139     LINE ret; 
140     ret.k=(y-y_)/(x-x_); ret.b=y-ret.k*x;
141     ret.x=min(x,x_); ret.x_=max(x,x_);
142     ret.y=min(y,y_); ret.y_=max(y,y_);
143     return ret;
144 }
145 void Del(int t){
146     if(ant[t].cake) Cake=0;
147     pd[ant[t].x][ant[t].y]=0;
148     now_tot--; tail--;
149     for(int k=t;k<tail;k++){
150         ant[k]=ant[k+1];
151     }
152 }
153 double Dis2(int k,LINE line){
154     int x=ant[k].x,y=ant[k].y;
155     if(x<line.x || x>line.x_ || y<line.y || y>line.y_) return 10.5;
156     double dis=fabs( (double)y-line.k*x-line.b )/sqrt( line.k*line.k+1.0);
157     return dis;
158 }
159 void Kill(int aim,int i){
160     if(ant[aim].x==bat[i].x && ant[aim].y==bat[i].y){
161         ant[aim].Hp-=D;
162         return;
163     }
164     else if(ant[aim].x==bat[i].x){
165         int le=min(ant[aim].y,bat[i].y),ri=max(ant[aim].y,bat[i].y);
166         for(int k=0;k<tail;k++){
167             if(ant[k].x==ant[aim].x && ant[k].y>=le && ant[k].y<=ri){
168                 ant[k].Hp-=D;
169             }
170             if(k==tail) break;
171         }
172         return;
173     }
174     else if(ant[aim].y==bat[i].y){
175         int le=min(ant[aim].x,bat[i].x),ri=max(ant[aim].x,bat[i].x);
176         for(int k=0;k<tail;k++){
177             if(ant[k].y==ant[aim].y && ant[k].x>=le && ant[k].x<=ri){
178                 ant[k].Hp-=D;
179             }
180             if(k==tail) break;
181         }
182         return; 
183     }
184     else{
185         LINE line=Get_line(ant[aim].x,ant[aim].y,bat[i].x,bat[i].y);
186         for(int k=0;k<tail;k++){
187  
188             if(Dis2(k,line)<=0.5){
189                 // if(k!=aim) printf("  %d-->%d too\n",i,ant[k].id);
190                 ant[k].Hp-=D;
191             }
192             if(k==tail) break;
193         }
194         return; 
195     }
196 }
197 void Fire(){
198     // printf("Aim::\n");
199     for(int i=1;i<=S;i++){
200         int aim=Find_a(i);
201         // printf("  %d-->%d\n",i,ant[aim].id);
202         if(aim==-1) continue;
203         Kill(aim,i);
204     } 
205     // cout<<endl;
206     // printf("Dead::\n");
207     for(int k=0;k<tail;k++){
208         if(ant[k].Hp<0){
209             // printf(" %d ",ant[k].id);
210             Del(k); k--;
211         }
212         if(k==tail) break;
213     }
214     // cout<<endl<<endl;
215 }
216 bool End(){
217     for(int k=0;k<tail;k++){
218         if(ant[k].x==0 && ant[k].y==0 && ant[k].cake){
219             Ed=1; return 1;
220         }
221     }
222     return 0;
223 }
224 void Update(){
225     for(int i=0;i<=n;i++){
226         for(int j=0;j<=m;j++){
227             mes[i][j]--;
228             if(mes[i][j]<0) mes[i][j]=0;
229         }
230     }
231     for(int k=0;k<tail;k++){
232         ant[k].age++;
233     }
234 }
235 void Print(){
236     if(Ed) printf("Game over after %d seconds\n",now_time);
237     else printf("The game is going on\n");
238     printf("%d\n",now_tot);
239     for(int k=0;k<tail;k++){
240         printf("%d %d %d %d %d\n",ant[k].age-1,ant[k].rank,ant[k].Hp,ant[k].x,ant[k].y);
241     }
242 }
243 void oott(){
244     printf("Ant:: \n");
245     for(int k=0;k<tail;k++) ant[k].A();
246     cout<<endl;
247 }
248 void work(){
249     for(int hh=1;hh<=T;hh++){ 
250         now_time++;
251         if(now_tot<6) Birth(hh);
252         // cout<<"--------------------------NEW--------------------------"<<endl;
253         // cout<<"now_time= "<<now_time<<"  tot=="<<now_tot<<endl;
254         // oott();
255         Make_mes(); 
256         Mov();
257         Fire(); 
258         if(End()) break;
259         Update();
260         // oott();
261     }
262     Print();
263 }
264 int main(){
265     // freopen("antbuster_ex.in","r",stdin);
266     // freopen("antbuster_ex.out","w",stdout);
267     // freopen("antbuster_ex.out","w",stdout);
268     init();
269     beg();
270     // cout<<px[100]<<endl;
271     work();
272 }
antbuster
在附上战斗日志（第二个测试点）
http://paste.ubuntu.org.cn/4280882
秒客网

BZOJ[1033] [ZJOI2008] 杀蚂蚁antbuster

相关文章
