[ZJOI 2008] 杀蚂蚁 (完整版) - 徐心雨 - 476935

记录编号	476935	评测结果	AWWWAAAWWA
题目名称	[ZJOI 2008] 杀蚂蚁 (完整版)	最终得分	50
用户昵称	徐心雨	是否通过	未通过
代码语言	C++	运行时间	0.287 s
提交时间	2017-11-27 21:30:26	内存使用	2.60 MiB
显示代码纯文本
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const double eps=1e-12;

int N,M;
int S,D,R;
int T;

struct TURRET
{
	int x,y;
}Turret[21];

struct ANT
{
	int x,y;
	int prex,prey;
	int level,tim,old;
	long long blood;
	bool cake;
	bool operator < (ANT p) const
	{
		return old>p.old;
	}
}A;

vector<ANT>Ant;
vector<ANT>::iterator it;

int Ant_sum,size;

int sum[9][9];

int map[9][9]; // 1 turret ,2 ant,3 cake

int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};

int Cake_ant=-1;

int BeHit[7];

long double BLOOD[200001];

bool Cake_Left;

int cut[7],cnt;

void read(int &x)
{
	x=0; char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}

void NewAnt()
{
	if(size>=6 || map[0][0]) return;
	Ant_sum++; 
	A.prex=A.prey=-1;
	A.blood=4*BLOOD[Ant_sum];
	A.level=(Ant_sum-1)/6+1;
	Ant.push_back(A);
	size++;
	map[0][0]=2;
}

void LeavePheromone()
{
	for(int i=0;i<size;++i)
	{
		if(Ant[i].blood<0) continue;
		if(Ant[i].cake) sum[Ant[i].x][Ant[i].y]+=5;
		else sum[Ant[i].x][Ant[i].y]+=2;
	}
}

bool inmap(int x,int y)
{
	if(x<0 || x>N || y<0 || y>M) return false;
	if(map[x][y]) return false;
	return true;
}

void AntMove()
{
	int aimx,aimy,aimd,mx;
	int nx,ny,nd;
	int tmpx,tmpy;
	
	for(int i=0;i<size;++i)
	{
		mx=-1;
		Ant[i].tim++;
		aimx=aimy=tmpx=tmpy=-1;
		for(int j=0;j<4;++j)
		{
			nx=Ant[i].x+dx[j];
			ny=Ant[i].y+dy[j];
			if(inmap(nx,ny))
			{
				if(sum[nx][ny]>mx)
				{
					if(Ant[i].prex==nx && Ant[i].prey==ny) 
					{
						tmpx=nx;
						tmpy=ny;
						continue;
					}
					mx=sum[nx][ny];
					aimx=nx; 
					aimy=ny;
					aimd=j;
				}
			}
		}
		bool flag=true;
		if(aimx==-1 && aimy==-1) 
		{
			if(Ant[i].prex==Ant[i].x && Ant[i].prey==Ant[i].y && tmpx!=-1)
			{
				aimx=tmpx;
				aimy=tmpy;
				flag=false;
			}
			else
			{
				Ant[i].prex=Ant[i].x;
				Ant[i].prey=Ant[i].y;
				if(Ant[i].x==N && Ant[i].y==M && Cake_Left)
				{
					Ant[i].cake=true;
					long long first=4*BLOOD[6*(Ant[i].level-1)+1];
					Ant[i].blood=min(Ant[i].blood+first/2,first);
					Cake_Left=false;
					Cake_ant=i;
				}
				continue;
			}
		}
		if(!(Ant[i].tim%5) && flag)
		{
			if(aimd==0) aimy--;
			else if(aimd==1) aimx--;
			else if(aimd==2) aimy++;
			else aimx++;
			nd=aimd;
			while(1)
			{
				nd--;
				if(nd<0) nd=3;
				nx=aimx+dx[nd];
				ny=aimy+dy[nd];
				if(inmap(nx,ny)) 
				{
					if(Ant[i].prex==nx && Ant[i].prey==ny) continue;
					aimx=nx;
					aimy=ny;
					break;
				}
			}
		}
		map[Ant[i].x][Ant[i].y]=0;
		Ant[i].prex=Ant[i].x;
		Ant[i].prey=Ant[i].y;
		Ant[i].x=aimx; 
		Ant[i].y=aimy;
		map[aimx][aimy]=2;
		if(aimx==N && aimy==M && Cake_Left)
		{
			Ant[i].cake=true;
			long long first=4*BLOOD[6*(Ant[i].level-1)+1];
			Ant[i].blood=min(Ant[i].blood+first/2,first);
			Cake_Left=false;
			Cake_ant=i;
		}
	}
}

double PointPointDis(int xa,int ya,int xb,int yb)
{
	return sqrt(1.0*(xa-xb)*(xa-xb)+(ya-yb)*(ya-yb));
}

double PointLineDis(int x,int y,double A,double B,double C)
{
	return abs(A*x+B*y+C)/sqrt(A*A+B*B);
}

bool dcmp(double x,double y)
{
	if(fabs(x-y)<eps) return true;
	return x<y;
}

void Attack(int t)
{
	double A,C,nA,nC;
	int Aim_ant;
	double mi,dis;
	double Interx;
	bool ok;
	memset(BeHit,0,sizeof(BeHit));
	for(int i=1;i<=S;++i)
	{	
		Aim_ant=-1;
		if(Cake_ant!=-1 && dcmp(PointPointDis(Turret[i].x,Turret[i].y,Ant[Cake_ant].x,Ant[Cake_ant].y),R)) 
		{
			Aim_ant=Cake_ant;
		}
		else
		{
			mi=100000;
			for(int j=0;j<size;++j)
			{
				dis=PointPointDis(Turret[i].x,Turret[i].y,Ant[j].x,Ant[j].y);
				if(dis<mi && dcmp(dis,R))
				{
					mi=dis;
					Aim_ant=j;
				}
			}
		}
		if(Aim_ant==-1) continue;
		if(abs(Ant[Aim_ant].x-Turret[i].x)<1e-9) 
		{
			for(int j=0;j<size;++j)
			{
				if(dcmp(abs(Ant[j].x-Ant[Aim_ant].x),0.5) && dcmp(Ant[j].y-0.5,max(Ant[Aim_ant].y,Turret[i].y)) && dcmp(min(Ant[Aim_ant].y,Turret[i].y),Ant[j].y+0.5)) 
				{
				//	if(t==T) printf("%d %d %d %d %d %d %d\n",i,Aim_ant,j,Ant[Aim_ant].x,Ant[Aim_ant].y,Ant[j].x,Ant[j].y);
					BeHit[j]++;
				}
			}
		}
		else if(abs(Ant[Aim_ant].y-Turret[i].y)<eps) 
		{
			for(int j=0;j<size;++j)
			{
				if(dcmp(abs(Ant[j].y-Ant[Aim_ant].y),0.5) && dcmp(Ant[j].x-0.5,max(Ant[Aim_ant].x,Turret[i].x)) && dcmp(min(Ant[Aim_ant].x,Turret[i].x),Ant[j].x+0.5)) 
				{
					//if(t==T) printf("%d %d %d %d %d %d %d\n",i,Aim_ant,j,Ant[Aim_ant].x,Ant[Aim_ant].y,Ant[j].x,Ant[j].y);
					BeHit[j]++;
				}
			}
		}
		else
		{
			A=1.0*(Ant[Aim_ant].y-Turret[i].y)/(Ant[Aim_ant].x-Turret[i].x);
			C=Turret[i].y-A*Turret[i].x;
			for(int j=0;j<size;++j)
			{
				if(j==Aim_ant) { BeHit[j]++; continue; }
				if(!dcmp(PointPointDis(Turret[i].x,Turret[i].y,Ant[j].x,Ant[j].y),R)) continue;
				ok=false;
				if(dcmp(PointLineDis(Ant[j].x,Ant[j].y,A,-1,C),0.5)) 
				{
					nA=-1.0/A; nC=Ant[j].y-nA*Ant[j].x;;
					Interx=(nC-C)/(A-nA);
					if(Interx>min(Ant[Aim_ant].x,Turret[i].x) && Interx<max(Ant[Aim_ant].x,Turret[i].x)) ok=true;
					else
					{
						if(dcmp(PointPointDis(Turret[i].x,Turret[i].y,Ant[j].x,Ant[j].y),0.5) || dcmp(PointPointDis(Ant[Aim_ant].x,Ant[Aim_ant].y,Ant[j].x,Ant[j].y),0.5)) ok=true;
					}
				}
				if(ok) 
				{
					//if(t==T) printf("%d %d %d %d %d %d %d\n",i,Aim_ant,j,Ant[Aim_ant].x,Ant[Aim_ant].y,Ant[j].x,Ant[j].y);
					BeHit[j]++;
				}
			}
		}
	}
	cnt=0;
/*	if(t==T)
	{
		for(int i=0;i<size;++i) printf("%d %d %I64d %d %d\n",Ant[i].old,Ant[i].level,Ant[i].blood,Ant[i].x,Ant[i].y);
	}*/
	for(int i=0;i<size;++i) 
	{
		Ant[i].blood-=1LL*BeHit[i]*D;
		if(Ant[i].blood<0) 
		{
			map[Ant[i].x][Ant[i].y]=0;
			cut[++cnt]=i;
			if(Cake_ant!=-1 && Ant[Cake_ant].blood<0)
			{
				Cake_Left=true;
				Cake_ant=-1;
			}
		}
	}
	int k;
	for(int i=1;i<=cnt;++i)
	{
		for(it=Ant.begin(),k=0;k<cut[i];++k,++it);
		Ant.erase(it);
		for(int j=i+1;j<=cnt;++j) cut[j]--;
		if(Cake_ant>cut[i]) Cake_ant--;
	}
	size-=cnt;
}

bool GameOver()
{
	if(Cake_ant==-1) return false;
	if(Ant[Cake_ant].x || Ant[Cake_ant].y) return false;
	return true;
}

void End()
{
	for(int i=0;i<=N;++i)
		for(int j=0;j<=M;++j) if(sum[i][j]) sum[i][j]--;
	for(int i=0;i<size;++i) 
	if(Ant[i].blood>=0) Ant[i].old++;
}

void Print()
{
	printf("%d\n",size);
	sort(Ant.begin(),Ant.end());
	for(int i=0;i<size;++i) printf("%d %d %lld %d %d\n",Ant[i].old,Ant[i].level,Ant[i].blood,Ant[i].x,Ant[i].y);
}

int main()
{	
	freopen("antbuster_ex.in","r",stdin);
	freopen("antbuster_ex.out","w",stdout);
	read(N); read(M);
	read(S); read(D); read(R);
	for(int i=1;i<=S;++i) 
	{
		read(Turret[i].x),read(Turret[i].y);
		map[Turret[i].x][Turret[i].y]=1;
	}
	Cake_Left=true;
	read(T);
	long double tmp=1;
	for(int i=1;i<=T;i+=6)
	{
		tmp*=1.1;
		for(int j=i;j<min(i+6,T+1);++j)  BLOOD[j]=tmp;
	}
	for(int i=1;i<=T;++i)
	{
		NewAnt();
		LeavePheromone();
		AntMove();
		Attack(i);
		
		if(GameOver()) 
		{
			printf("Game over after %d seconds\n",i);
			Print();
			return 0;
		}
		End();
	}
	puts("The game is going on");
	Print();
}