兩個**錯誤調(diào)了一整天...

1.pubp函數(shù)括號匹配錯了

2.精度常數(shù)類型開成了int

就是一個大模擬,別的沒什么好講的,講一講我判斷圓和線是否有交點的pubp函數(shù),個人認為很容易理解。

其實就是不想動腦子才用了簡單粗暴的辦法

我們這樣記錄一條線段:

當(dāng)該線段不與\(x\)軸垂直,我們記錄\({k,b,l,r}\),表示這條線段所在的直線解析式為\(y=kx b\),\(x\)坐標(biāo)的范圍為\([l,r]\)。

當(dāng)該線段與\(x\)軸垂直,我們記錄\(k,l,r\),表示這條線段所在的直線為\(x=k\),\(y\)坐標(biāo)的范圍為\([l,r]\)。

然后我們設(shè)點\(p(u,v)\),則以\(p\)為圓心,1為直徑(\(\frac{1}{2}\)為半徑)的圓的方程為\((x-u)^2 (y-v)^2=\frac{1}{4}\)。

我們要求線段和點\(p\)是否有交點,考慮求線段所在直線和\(p\)是否有交點,以及是否有交點的坐標(biāo)在線段的坐標(biāo)范圍內(nèi)。

當(dāng)線段不與\(x\)軸垂直,我們設(shè)線段為\(k,b,l,r\)。

設(shè)交點坐標(biāo)\((x,y)\)則有

\(kx b=y\)(①)

\((x-u)^2 (y-v)^2=\frac{1}{4}\)(②)

展開②式

\(x^2-2ux u^2 y^2-2vy v^2-\frac{1}{4}=0\)

代入\(y=kx b\)

\(x^2-2ux u^2 (kx b)^2-2v(kx b) v^2-\frac{1}{4}=0\)

\(x^2-2ux u^2 k^2x^2 2bkx b^2-2vkx-2vb v^2-\frac{1}{4}=0\)

即

\((k^2 1)x^2 (2bk-2vk-2u)x u^2 b^2-2vb v^2-\frac{1}{4}\)

那么有\(zhòng)(x=\frac{-(2bk-2vk-2u)\pm\sqrt{(2bk-2vk-2u)^2-4(k^2 1)(u^2 b^2-2vb v^2-\frac{1}{4})}}{2(k^2 1)}\)

設(shè)\(pt_1=-(2bk-2vk-2u),pt_2=\sqrt{(2bk-2vk-2u)^2-4(k^2 1)(u^2 b^2-2vb v^2-\frac{1}{4})},pt_3=2(k^2 1)\)

則當(dāng)\(l\le\frac{pt_1 pt_2}{pt_3}\le r\)或\(l\le\frac{pt_1-pt_2}{pt_3}\le r\)時

線段與圓有交點。

當(dāng)線段與\(x\)軸垂直,我們設(shè)線段為\(k,l,r\)。

設(shè)交點坐標(biāo)\((k,y)\)則有

\((k-u)^2 (y-v)^2=\frac{1}{4}\)

\((y-v)^2=\frac{1}{4}-(k-u)^2\)

\(y=v\pm\sqrt{\frac{1}{4}-(k-u)^2}\)

設(shè)\(pt_1=\sqrt{\frac{1}{4}-(k-u)^2}\)

則當(dāng)\(l\le v pt_1\le r\)或\(l\le v-pt_1\le r\)時

線段與圓有交點。

當(dāng)然這種做法也有一定的缺點,比如式子比較復(fù)雜,容易寫錯或者出現(xiàn)精度問題。

其余部分直接模擬就好了。

code:

代碼不長,剛好130行

使用vector來儲存螞蟻

#include<bits/stdc  .h>
#define sqr(x) (x)*(x)
using namespace std;
const double _=1e-7;
const int W[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
struct line{//y=kx b(l<=x<=r)(tag=0);x=k(l<=y<=r)(tag=1)
    double k,b,l,r;
    int tag;
};
struct point{
    int x,y;
}turret[25];
struct ant{
    point p,lst;
    int hp,mxhp,age,level;
};
bool equ(const double&x,const double&y){
    return abs(x-y)<=_;
}
bool les(const double&x,const double&y){
    return y-x>_;
}
bool eol(const double&x,const double&y){
    return equ(x,y)||les(x,y);
}
double dis(point a,point b){
    return sqrt(sqr(a.x-b.x) sqr(a.y-b.y));
}
line solve(point a,point b){//求出線段ab的表示
    if(a.x==b.x)return(line){a.x,0,min(a.y,b.y),max(a.y,b.y),1};
    else{
        double k=1.0*(a.y-b.y)/(a.x-b.x);
        return(line){k,a.y-k*a.x,min(a.x,b.x),max(a.x,b.x),0};
    }
}
bool pubp(line l,point p){//判斷線段l與以點p為圓心,1為直徑的圓是否有交點
    if(!l.tag){
        if(sqr(2*l.k*l.b-2*p.y*l.k-2*p.x)-4*(sqr(l.k) 1)*(sqr(p.x) sqr(l.b)-2*p.y*l.b sqr(p.y)-1.0/4.0)<0)return false;
        double pt1=-(2*l.k*l.b-2*p.y*l.k-2*p.x),pt2=sqrt(sqr(2*l.k*l.b-2*p.y*l.k-2*p.x)-4*(sqr(l.k) 1)*(sqr(p.x) sqr(l.b)-2*p.y*l.b sqr(p.y)-1.0/4.0)),pt3=2*(sqr(l.k) 1);
        return(eol(l.l,(pt1 pt2)/pt3)&&eol((pt1 pt2)/pt3,l.r)||eol(l.l,(pt1-pt2)/pt3)&&eol((pt1-pt2)/pt3,l.r));
    }else{
        if(sqr(l.k-p.x)>1.0/4.0)return false;
        int pt1=sqrt(1.0/4.0-sqr(l.k-p.x));
        return(eol(l.l,p.y pt1)&&eol(p.y pt1,l.r))||(eol(l.l,p.y-pt1)&&eol(p.y-pt1,l.r));
    }
}
int n,m,s,d,r,t,ph[10][10],mp[10][10];
int stot,tca=-1;
vector<ant>a;
void getp(point&x){//讀入點 
    int t1,t2;
    scanf("%d%d",&t1,&t2),x.x=t1,x.y=t2;
    mp[t1][t2]=1;
}
double POW(double x,int y){//快速冪 
    double tot=1;
    while(y)y&1?tot*=x:0,x*=x,y>>=1;
    return tot;
}
void Spawn(){//生成螞蟻 
    if(mp[0][0])return;
    for(int i=0;i<a.size();  i)if(a[i].p.x==0&&a[i].p.y==0)return;
      stot;
    int tmp=(int)(4.0*POW(1.1,(stot 5)/6));
    a.push_back((ant){(point){0,0},(point){0,0},tmp,tmp,0,(stot 5)/6});
}
void Put_pheromone(){//留下信息素 
    for(int i=0;i<a.size();  i)ph[a[i].p.x][a[i].p.y] =(tca==i?5:2);
}
bool Blank(int x,int y){//判斷一個點是否為空(即沒有炮塔或者螞蟻) 
    if(mp[x][y])return false;
    for(int i=0;i<a.size();  i)if(a[i].p.x==x&&a[i].p.y==y)return false;
    return true;
}
bool Check(int id,int x,int y){//判斷一個點是否可行 
    return (x!=a[id].lst.x||y!=a[id].lst.y)&&0<=x&&x<=n&&0<=y&&y<=m&&Blank(x,y);
}
void Move_to(int id,int x,int y){//將螞蟻移動到點(x,y) 
    a[id].lst=a[id].p,a[id].p=(point){x,y};
}
void Move(){//移動螞蟻 
    for(int i=0;i<a.size();  i){
        int mxp=-1,tw,tx,ty;
        for(int w=0;w<4;  w)tx=a[i].p.x W[w][0],ty=a[i].p.y W[w][1],Check(i,tx,ty)&&ph[tx][ty]>mxp?mxp=ph[tx][ty],tw=w:0;
        if(mxp<0){
            a[i].lst=a[i].p;
            continue;
        }else{
            if((a[i].age 1)%5==0)while(tw=(tw 3)%4,!Check(i,a[i].p.x W[tw][0],a[i].p.y W[tw][1]));
            Move_to(i,a[i].p.x W[tw][0],a[i].p.y W[tw][1]);
        }
    }
}
void Shoot(point u,point v){//從點u發(fā)射激光到點v 
    line ray=solve(u,v);
    for(int i=0;i<a.size();  i)if(pubp(ray,a[i].p))a[i].hp-=d;
}
void Attack(){//炮塔攻擊 
    for(int i=1;i<=s;  i){
        if(tca!=-1&&eol(dis(turret[i],a[tca].p),(double)r))Shoot(turret[i],a[tca].p);
        else{
            double mnd=r 1,td;int sa;
            for(int j=0;j<a.size();  j)td=dis(turret[i],a[j].p),les(td,mnd)?mnd=td,sa=j:0;
            if(eol(mnd,r))Shoot(turret[i],a[sa].p);
        }
    }
}
void End(int T){//游戲結(jié)束 
    printf("Game over after %d seconds\n%d\n",T,a.size());
    for(int i=0;i<a.size();  i)printf("%d %d %d %d %d\n",a[i].age,a[i].level,a[i].hp,a[i].p.x,a[i].p.y);
    exit(0);
}
int main(){
    scanf("%d%d%d%d%d",&n,&m,&s,&d,&r);
    for(int i=1;i<=s;  i)getp(turret[i]);
    scanf("%d",&t);
    for(int Time=1;Time<=t;  Time){
        if(a.size()<6)Spawn();
        Put_pheromone(),Move();
        for(int i=0;i<a.size();  i)if(a[i].p.x==n&&a[i].p.y==m&&tca==-1)tca=i,a[i].hp=min(a[i].mxhp,a[i].hp a[i].mxhp/2);
        Attack();
        for(int i=0;i<a.size();  i)if(a[i].hp<0)a.erase(a.begin() i),tca==i?tca=-1:0,tca>i?--tca:0,--i;
        for(int i=0;i<a.size();  i)if(tca==i&&a[i].p.x==0&&a[i].p.y==0)End(Time);
        for(int i=0;i<=n;  i)for(int j=0;j<=m;  j)ph[i][j]?--ph[i][j]:0;
        for(int i=0;i<a.size();  i)  a[i].age;
    }
    printf("The game is going on\n%d\n",a.size());
    for(int i=0;i<a.size();  i)printf("%d %d %d %d %d\n",a[i].age,a[i].level,a[i].hp,a[i].p.x,a[i].p.y);
    return 0;
}