[ZJOI 2008] 杀蚂蚁 (完整版) - AntiLeaf - 324581

记录编号	324581	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2008] 杀蚂蚁 (完整版)	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.634 s
提交时间	2016-10-18 15:04:10	内存使用	41.22 MiB
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
const double eps=1e-6;
struct ANTS{
	int age,life,level,bornlife,x,y,lastx,lasty;
	bool havecake;
	ANTS(){}
	bool operator<(const ANTS &a)const{
		return age>a.age;
	}
	void getcake(){
		havecake=true;
		life+=(bornlife>>1);
		if(life>bornlife)life=bornlife;
	}
}a[1000010];
struct TOWER{int x,y;}b[100010];
void bornant();
void leavesth();
void moveants();
void attack();
void judgeend();
void endofround();
void printwin();
void printlose();
void moveit(int);
bool can(int,int,int);
void moveto(int,int,int);
void trytoattack(int);
double dis(int,int);
double dis3(int,int,int);
void hitant(int);
void dieant(int);
void maintainants();
int dcmp(double,double);
int n,m,k,d,r;
bool ant[1010][1010],tow[1010][1010],lose;
int tim,T,in[1010][1010];
int cak;
int cnt=0,head=1,tail=1;
int main(){
#define MINE
#ifdef MINE
	freopen("antbuster_ex.in","r",stdin);
	freopen("antbuster_ex.out","w",stdout);
#endif
	scanf("%d%d%d%d%d",&n,&m,&k,&d,&r);
	for(int i=1;i<=k;i++){
		scanf("%d%d",&b[i].x,&b[i].y);
		tow[b[i].x][b[i].y]=true;
	}
	scanf("%d",&T);
	for(tim=1;tim<=T;tim++){
		//printf("TIME:%d\n",tim);
		bornant();//printf("1");
		leavesth();//printf("2");
		moveants();//printf("3");
		attack();//printf("4");
		judgeend();//printf("5");
		if(lose)break;
		endofround();//printf("6\n");
		//printf("cnt=%d\n",cnt);
		//printwin();printf("\n");
	}
	if(lose)printlose();
	else printwin();
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#endif
	return 0;
}
void bornant(){
	if(cnt<6&&!ant[0][0]){
		//printf("%d borns\n",tail);
		cnt++;
		a[tail].age=1;
		a[tail].level=(tail-1)/6+1;
		a[tail].life=a[tail].bornlife=(int)(4*pow(1.1,a[tail].level));
		a[tail].x=a[tail].y=0;
		ant[0][0]=true;
		a[tail].lastx=a[tail].lasty=-1;
		tail++;
	}
}
void leavesth(){
	for(int i=head;i!=tail;i++){
		if(a[i].havecake)in[a[i].x][a[i].y]+=5;
		else in[a[i].x][a[i].y]+=2;
	}
}
void moveants(){
	for(int i=head;i!=tail;i++)moveit(i);
}
void attack(){
	for(int j=1;j<=k;j++)trytoattack(j);
	for(int i=head;i!=tail;i++)dieant(i);
}
void judgeend(){
	if(cak&&!a[cak].x&&!a[cak].y)lose=true;
	//    &   一开始没看出来......论逻辑与与按位与的差别......
}
void endofround(){
	/*for(int i=0;i<=n;i++){
		for(int j=0;j<=m;j++)printf("%d ",in[i][j]);
		printf("\n");
	}printf("\n");*/
	for(int i=0;i<=n;i++)for(int j=0;j<=m;j++)if(in[i][j])in[i][j]--;
	for(int i=head;i!=tail;i++)a[i].age++;
	/*for(int i=0;i<=n;i++){
		for(int j=0;j<=m;j++)printf("%d ",in[i][j]);
		printf("\n");
	}
	printf("\n");
	for(int i=0;i<=n;i++){
		for(int j=0;j<=m;j++)printf("%d ",ant[i][j]);
		printf("\n");
	}*/
}
void printwin(){
	printf("The game is going on\n");
	printf("%d\n",cnt);
	for(int i=head;i!=tail;i++){
		/*if(cak!=i)*/printf("%d %d %d %d %d\n",a[i].age-1,a[i].level,a[i].life,a[i].x,a[i].y);
		//else printf("id=%d %d %d %d %d %d !!!cake\n",i,a[i].age-1,a[i].level,a[i].life,a[i].x,a[i].y);
	}
}
void printlose(){
	printf("Game over after %d seconds\n",tim);
	printf("%d\n",cnt);
	for(int i=head;i!=tail;i++){
		printf("%d %d %d %d %d\n",a[i].age-1,a[i].level,a[i].life,a[i].x,a[i].y);
	}
}
void moveit(int i){
	//printf("moveit(%d) at(%d,%d)\n",i,a[i].x,a[i].y);
	bool ok[4]={false},OK=false;
	int x,y,tmp=0;
	for(int k=0;k<4;k++){
		x=a[i].x+dx[k];
		y=a[i].y+dy[k];
		ok[k]=can(x,y,i);
		//printf("x=%d y=%d ok=%d\n",x,y,ok[k]);
		if(ok[k]){
			OK=true;
			if(in[x][y]>tmp){
				//printf("clear ok\n");
				memset(ok,false,sizeof(ok));
				ok[k]=true;
				tmp=in[x][y];
			}
		}
	}
	//for(int k=0;k<4;k++)printf("%d ",ok[k]);printf("\n");
	if(!OK){
		moveto(a[i].x,a[i].y,i);
		return;
	}
	if(a[i].age%5){//printf("-");
		for(int k=0;k<4;k++)if(ok[k]){
			moveto(a[i].x+dx[k],a[i].y+dy[k],i);
			break;
		}
	}
	else{//This is a bit complex...
		int k=0;//printf("--");
		for(;!ok[k];k++);
		for(k=(k+3)%4;!can(a[i].x+dx[k],a[i].y+dy[k],i);k=(k+3)%4);
		moveto(a[i].x+dx[k],a[i].y+dy[k],i);
	}
}
bool can(int x,int y,int i){
	if(x<0||y<0||x>n||y>m)return false;
	if(ant[x][y]||tow[x][y])return false;
	if(x==a[i].lastx&&y==a[i].lasty)return false;
	return true;
}
void moveto(int x,int y,int i){//and get cake.
	//printf("%d from (%d,%d) to (%d,%d)\n",i,a[i].x,a[i].y,x,y);
	if(x==a[i].x&&y==a[i].y){
		a[i].lastx=a[i].lasty=-1;
		if(!cak&&x==n&&y==m){
			//printf("%d gets the cake\n",i);
			a[i].getcake();
			cak=i;
		}
	}
	else{
		a[i].lastx=a[i].x;
		a[i].lasty=a[i].y;
		ant[a[i].x][a[i].y]=false;
		ant[x][y]=true;
		a[i].x=x;
		a[i].y=y;
		if(!cak&&x==n&&y==m){
			//a[i].havecake=true;
			//printf("%d gets the cake\n",i);
			a[i].getcake();
			cak=i;
		}
	}
}
void trytoattack(int j){//Tower j trys to attack.
	//printf("trytoattack(%d)\n",j);
	int target=0;
	if(cak&&dcmp(dis(cak,j),r)<=0)target=cak;
	if(!target){
		for(int i=head;i!=tail;i++)if(dcmp(dis(i,j),r)<=0&&(!target||dcmp(dis(i,j),dis(target,j))<0))target=i;
	}
	if(!target)return;
	hitant(target);
	//printf("hit target(%d)\n",target);
	for(int i=head;i!=tail;i++)if(i!=target&&dcmp(dis(i,j),dis(target,j))<0&&dcmp(dis3(i,j,target),0.5)<=0){
		TOWER A,B;
		A.x=a[target].x-b[j].x;
		A.y=a[target].y-b[j].y;
		B.x=a[i].x-b[j].x;
		B.y=a[i].y-b[j].y;
		if(A.x*B.x+A.y*B.y<=0)continue;
		hitant(i);
	}
}
double dis(int i,int j){//The distance of ant i and tower j
	return sqrt((a[i].x-b[j].x)*(a[i].x-b[j].x)+(a[i].y-b[j].y)*(a[i].y-b[j].y));
}
double dis3(int i,int j,int ii){//Ant i's distance to the tower hitting ii
	TOWER A,B;//In fact these are only two points,2333
	A.x=a[i].x-b[j].x;
	A.y=a[i].y-b[j].y;
	B.x=a[ii].x-a[i].x;
	B.y=a[ii].y-a[i].y;
	return abs(A.x*B.y-B.x*A.y)/dis(ii,j);
}
void hitant(int i){
	//printf("%d is hitted\n",i);
	a[i].life-=d;
	//if(a[i].life<0)dieant(i);
}
void dieant(int x){
	if(a[x].life>=0)return;
	//printf("%d die\n",x);
	if(a[x].havecake)cak=0;
	ant[a[x].x][a[x].y]=false;
	swap(a[head],a[x]);
	head++;
	cnt--;
	maintainants();
}
void maintainants(){
	sort(a+head,a+tail);
	cak=0;
	for(int i=head;i!=tail;i++)if(a[i].havecake)cak=i;
}
int dcmp(double a,double b){
	if(fabs(a-b)<=eps)return 0;
	return a<b?-1:1;
}
/*
8 8
2 10 1
7 8
8 6
5
Answer:
The game is going on
5
5 1 4 1 4
4 1 4 0 4
3 1 4 0 3
2 1 4 0 2
1 1 4 0 1
*/