当前位置：首页 > article >正文

bzoj1033 [ZJOI2008]杀蚂蚁antbuster

article 2025/9/16 1:40:03

题目

zjoi。。。一道神题，大模拟题目。

不想写233。

贴一个hzwer的代码。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,s,tur_d,r,T,born;
int in[11][11];
int xx[4]={0,1,0,-1},yy[4]={1,0,-1,0};
bool getcake,mp[11][11];
struct tur{int x,y;}tur[31];
struct ant{int lev,hp,age,x,y,lx,ly,mx;bool live,cake;}a[11];
struct point{int x,y;};
struct line{point a,b;}l;inline 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;}
inline 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(tur[x].x-a[y].x)+sqr(tur[x].y-a[y].y);}
inline double getdis(int x,int y)
{return sqrt(cdis(x,y));}
inline bool cmp(const ant &a,const ant &b){return a.age>b.age;}
inline char nc()
{static char buf[100000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{char c=nc();int x=0,b=1;for(;!(c<='9'&&c>='0');c=nc())if(c=='-')b=-1;for(;c<='9'&&c>='0';c=nc())x=x*10+c-'0';return x*b;
}
inline void write(int x)
{int L=0;char s[15];if(!x)putchar('0');else while(x)s[++L]=x%10+'0',x/=10;for(int i=L;i>=1;i--)putchar(s[i]);putchar('\n');
}
inline void bornint(int k)
{int l=born/6+1;a[k].lev=l;a[k].hp=a[k].mx=int(4*pow(1.1,l));a[k].age=0;a[k].live=1;a[k].x=a[k].y=a[k].lx=a[k].ly=0;mp[0][0]=1;born++;
}
inline bool jud(int x,int y,int lx,int ly)
{if(mp[x][y]||x<0||y<0||x>n||y>m)return 0;if(x==lx&&y==ly)return 0;return 1;
}
inline void move(int k,int dir)
{int x=a[k].x,y=a[k].y;if(dir==-1){a[k].lx=x;a[k].ly=y;return;}int nowx=x+xx[dir],nowy=y+yy[dir];mp[x][y]=0;mp[nowx][nowy]=1;a[k].lx=x;a[k].ly=y;a[k].x=nowx;a[k].y=nowy;
}
inline void spmove(int k,int dir)
{int x=a[k].x,y=a[k].y,lx=a[k].lx,ly=a[k].ly;for(int i=(dir-1+4)%4;;i=(i-1+4)%4){int nowx=x+xx[i],nowy=y+yy[i];if(jud(nowx,nowy,lx,ly)){move(k,i);return;}}
}
inline void premove(int k)
{int x=a[k].x,y=a[k].y,lx=a[k].lx,ly=a[k].ly;int mx=-0x7fffffff,dir=-1;for(int i=0;i<4;i++){int nowx=x+xx[i],nowy=y+yy[i];if(jud(nowx,nowy,lx,ly)&&mx<in[nowx][nowy])mx=in[nowx][nowy];}for(int i=0;i<4;i++){int nowx=x+xx[i],nowy=y+yy[i];if(jud(nowx,nowy,lx,ly)&&(mx==in[nowx][nowy])){dir=i;break;}}if((a[k].age+1)%5!=0||dir==-1)move(k,dir);else spmove(k,dir);
}
inline bool 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 k)
{int tmp=-1,dis=0x7fffffff;for(int i=1;i<=6;i++)if(a[i].live){int d=cdis(k,i);if(d<=r*r){ if(a[i].cake)tmp=i;else if(!a[tmp].cake&&d<dis){dis=d;tmp=i;}}}if(tmp==-1)return;l.a.x=tur[k].x;l.a.y=tur[k].y;l.b.x=a[tmp].x;l.b.y=a[tmp].y;for(int i=1;i<=6;i++)if(a[i].live){if(cross(a[i].x,a[i].y))a[i].hp-=tur_d;}
}
inline bool solve(int t)
{if(!mp[0][0])for(int i=1;i<=6;i++)if(!a[i].live){bornint(i);break;}sort(a+1,a+7,cmp);for(int i=1;i<=6;i++)if(a[i].live){int x=a[i].x,y=a[i].y;if(a[i].cake)in[x][y]+=5;else in[x][y]+=2;}for(int i=1;i<=6;i++)if(a[i].live)premove(i);if(!getcake)for(int i=1;i<=6;i++)if(a[i].live)if(a[i].x==n&&a[i].y==m){a[i].cake=1;getcake=1;a[i].hp=min(a[i].mx,a[i].hp+a[i].mx/2);}for(int i=1;i<=s;i++)attack(i);for(int i=1;i<=6;i++)if(a[i].live)if(a[i].hp<0){mp[a[i].x][a[i].y]=0;a[i].live=0;if(a[i].cake)a[i].cake=getcake=0;}if(getcake)for(int i=1;i<=6;i++)if(a[i].live)if(a[i].x==0&&a[i].y==0&&a[i].cake)return 1;for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)if(in[i][j]>0)in[i][j]--;for(int i=1;i<=6;i++)if(a[i].live)a[i].age++;return 0;
}
inline void ini()
{n=read(),m=read();s=read(),tur_d=read(),r=read();for(int i=1;i<=s;i++){tur[i].x=read(),tur[i].y=read();mp[tur[i].x][tur[i].y]=1;}T=read();
}
inline void print()
{int cot=0;sort(a+1,a+7,cmp);for(int i=1;i<=6;i++)if(a[i].live)cot++;printf("%d\n",cot);for(int i=1;i<=6;i++)if(a[i].live)printf("%d %d %d %d %d\n",a[i].age,a[i].lev,a[i].hp,a[i].x,a[i].y);} 
int main()
{//freopen("in.txt","r",stdin);ini();for(int i=1;i<=T;i++)if(solve(i)){printf("Game over after %d seconds\n",i);print();return 0;}printf("The game is going on\n");print(); return 0;
}