【模拟】【计算几何】[ZJOI2008][HYSBZ/BZOJ1033]杀蚂蚁antbuster_weixin_30576827的博客-程序员宝宝

题目链接

分析

这道题,是一道十分优(e)秀(xin)的模拟题。
有一些注意事项:

  1. 一边看题一边写,不要把题目读错了
  2. 一切活动都要严格按照这个顺序来,仔细理解题目所给的意思。这是每一秒钟的活动顺序
  3. 注意蚂蚁移动的顺序。
  4. 所有炮塔是同时攻击的。
  5. 这里写图片描述这里写图片描述在模拟中掺杂了计算几何。

知道了这些,写不写得出来,就看你的实(ren)力(pin)了。

代码

#include<cstdio>
#include<algorithm>
#include<set>
#include<iostream>
#include<cmath>
#include<stack>
#define MAXS 20
#define INF 0x7fffffff
#define MAXN 8
using namespace std;
#define MAXT 200000
set<int>se;
int n,m,s,d,r,x[MAXS+10],y[MAXS+10],cnt,b[MAXT+10],t,f[MAXN+10][MAXN+10],cake,num,bt[MAXT+10];
double k1,b1,mypow[MAXT+10];
pair<int,int>pos[MAXT+10],fr[MAXT+10];
int mat[MAXN+10][MAXN+10],dir[4][2]={
     {
     0,1},{
     1,0},{
     0,-1},{-1,0}},tms;
void Read(int &x){
    char c;
    while(c=getchar(),c!=EOF)
        if(c>='0'&&c<='9'){
            x=c-'0';
            while(c=getchar(),c>='0'&&c<='9')
                x=x*10+c-'0';
            ungetc(c,stdin);
            return;
        }
}
void read(){
    int i;
    Read(n),Read(m),Read(s),Read(d),Read(r);
    for(i=1;i<=s;i++){
        Read(x[i]),Read(y[i]);
        mat[x[i]][y[i]]=-1;
    }
    Read(t);
}
inline int Get_sqdist(int x1,int y1,int x2,int y2){
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
inline double Get_dist(int x1,int y1,int x2,int y2){
    return sqrt(Get_sqdist(x1,y1,x2,y2));
}
void born(){
    if(cnt<6&&!mat[0][0]){
        num++;
        cnt++;
        bt[num]=tms;
        mat[0][0]=num;
        pos[num]=make_pair(0,0);
        b[num]=4*mypow[(num+5)/6];
        se.insert(num);
    }
}
void move(){
    int tx,ty,d,mx,maxdir,ttx,tty,cc;
    set<int>::iterator j;
    for(j=se.begin();j!=se.end();j++){
        tx=pos[*j].first,ty=pos[*j].second;
        f[tx][ty]+=(*j==cake?5:2);
        mx=-1,maxdir=-1,cc=0;
        for(d=0;d<4;d++){
            ttx=tx+dir[d][0],tty=ty+dir[d][1];
            if(ttx>=0&&ttx<=n&&tty>=0&&tty<=m&&!mat[ttx][tty]&&fr[*j]!=make_pair(ttx,tty))
                if(f[ttx][tty]>mx)
                    maxdir=d,mx=f[ttx][tty];
        }
        if(maxdir==-1){
            fr[*j]=pos[*j];
            continue;
        }
        if((tms-bt[*j]+1)%5==0)
            for(maxdir=(maxdir+3)%4;;maxdir=(maxdir+3)%4){
                ttx=tx+dir[maxdir][0],tty=ty+dir[maxdir][1];
                if(ttx>=0&&ttx<=n&&tty>=0&&tty<=m&&!mat[ttx][tty]&&fr[*j]!=make_pair(ttx,tty))
                    break;
            }
        fr[*j]=pos[*j];
        ttx=tx+dir[maxdir][0],tty=ty+dir[maxdir][1];
        mat[tx][ty]=0;
        pos[*j]=make_pair(ttx,tty);
        mat[ttx][tty]=*j;
    }
    if(!cake&&mat[n][m]){
        cake=mat[n][m];
        b[mat[n][m]]=min(b[mat[n][m]]+(int)(4*mypow[(mat[n][m]+5)/6])/2,(int)(4*mypow[(mat[n][m]+5)/6]));
    }
}
double cross_product(int x1,int y1,int x2,int y2){
 return x1*y2-x2*y1;
}
bool cross(int i,int tgt,int num){
    int x1,y1,x2,y2,x3,y3;
    x1=x[i],y1=y[i],x2=pos[tgt].first,y2=pos[tgt].second,x3=pos[num].first,y3=pos[num].second;
    int mnx=min(x1,x2),mxx=max(x1,x2),mny=min(y1,y2),mxy=max(y1,y2);
    if(x3<mnx||x3>mxx||y3<mny||y3>mxy)
        return 0;
    if(fabs(cross_product(x1-x3,y1-y3,x2-x3,y2-y3))<=0.5*Get_dist(x1,y1,x2,y2))
        return 1;
    return 0;
}
void attack(){
    int i,tgt,mi,t;
    set<int>::iterator j;
    for(i=1;i<=s;i++){
        if(cake&&Get_sqdist(x[i],y[i],pos[cake].first,pos[cake].second)<=r*r)
            tgt=cake;
        else{
            tgt=0,mi=r*r+1;
            for(j=se.begin();j!=se.end();j++)
                if((t=Get_sqdist(x[i],y[i],pos[*j].first,pos[*j].second))<mi)
                    tgt=*j,mi=t;
            if(!tgt)
                continue;
        }
        b[tgt]-=d;
        for(j=se.begin();j!=se.end();j++)
            if(*j!=tgt&&cross(i,tgt,*j))
                b[*j]-=d;
    }
}
bool beh_attack(){
    set<int>::iterator j;
    stack<int>ss;
    for(j=se.begin();j!=se.end();j++)
        if(b[*j]<0){
            ss.push(*j);
            mat[pos[*j].first][pos[*j].second]=0;
            cnt--;
        }
    while(!ss.empty()){
        se.erase(ss.top());
        ss.pop();
    }
    if(cake){
        if(b[cake]<0)
            cake=0;
        else if(!pos[cake].first&&!pos[cake].second)
            return 1;
    }
    return 0;
}
void ending(){
    int i,j;
    for(i=0;i<=n;i++)
        for(j=0;j<=m;j++)
            if(f[i][j])
                f[i][j]--;
}
bool solve(){
    for(tms=1;tms<=t;tms++){
        born();
        move();
        attack();
        if(beh_attack())
            return 1;
        ending();
    }
    return 0;
}
void print(){
    printf("%d\n",cnt);
    for(set<int>::iterator j=se.begin();j!=se.end();j++)
        printf("%d %d %d %d %d\n",tms-bt[*j],(*j+5)/6,b[*j],pos[*j].first,pos[*j].second);
}
void prepare(){
    mypow[0]=1;
    for(int i=1;i<=t;i++)
        mypow[i]=mypow[i-1]*1.1;
}
int main()
{
    read();
    prepare();
    if(solve())
        printf("Game over after %d seconds\n",tms);
    else
        puts("The game is going on");
    print();
}

转载于:https://www.cnblogs.com/outerform/p/5921861.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_30576827/article/details/97896453

智能推荐

Spring、Mybatis、Spring MVC整合实例_Jstack的博客-程序员宝宝

Spring、Mybatis、Spring MVC整合实例笔记源码地址:https://gitee.com/name168/SSM_Demo 1、Maven web项目创建(IDEA) 2、SSM整合 2.1、maven引入需要的jar包 2.2、Spring与MyBatis的整合 2.2.1、创建JDBC链接信息属性文件 2.2.2、创建spring-mybatis.xml配置文...

(day01)02_数据类型的本质_guozipi的博客-程序员宝宝

#include &amp;lt;stdio.h&amp;gt;#include &amp;lt;stdlib.h&amp;gt;int main(){ int a; int b[10]; /* b, &amp;amp;b的数组类型不一样 b是数组首元素地址,一个元素占4个字节,+1,+4字节 &amp;amp;b是整个数组的首地址,一个数组占4*10个字节,&amp;amp;b+1,是+40个字节 */ printf...

vue面试之“防抖和节流”_空投在我怀里的博客-程序员宝宝

防抖: 就是指触发事件后在n秒内函数只能执行一次,如果在n秒内又触发了事件,则会重新计算函数执行时间。例如:设定1000毫秒执行,当你触发事件了,他会1000毫秒后执行,但是在还剩500毫秒的时候你又触发了事件,那就会重新&lt;body&gt; &lt;input type="text" class="ipt" /&gt; &lt;script&gt; var timerId = null document.querySelector('.ipt').on

justicme的第一个博客_justicme的博客-程序员宝宝

justicme的第一个博客标题的创建快捷键:Ctrl+Shift+H高亮显示这是高亮显示实现方法:如何改变文本的样式强调文本 强调文本加粗文本 加粗文本标记文本删除文本引用文本H2O is是液体。210 运算结果是 1024.新的变化我们对Markdown编辑器进行了一些功能拓展与语法支持,除了标准的Markdown编辑器功能,我们增加了如下几点新功能,帮助你用它写博客:全新的界面设计 ,将会带来全新的写作体验;在创作中心设置你喜爱的代码高亮样式,Markdown

MPU6050 Motion Driver 6.12自检校准偏差保存_介子納须弥的博客-程序员宝宝

MPU6050或者MPU9250的移植就没啥了,主要是提供IIC读写函数,提供时间戳,修改宏。如果有必要,根据PCB的方向和实际安装的方向修改旋转矩阵。这个官方都有提供手册指导的。主要是想说关于MPU6050 motion driver6.12版本 DMP提供了一个自检和校准的功能。run_self_test();if(mpu_run_self_test(gyro, accel)==0...

Centos/linux安装vmware-tools工具报错解决、yum配置_cixiaobi8104的博客-程序员宝宝

Centos/linux安装vmware-tools工具报错解决、yum配置1、vmware tools”就等于装虚拟机的显卡驱动,如果不装“vmware tools”,则虚拟机的分辨率会很低且无法...

随便推点

Spring MVC简介-1_意向天开的博客-程序员宝宝

Spring MVC是在MVC设计思想的基础上产生的一种框架,可以理解为Spring的一个子模块,相当于Spring AOP这种一.Spring MVC主要组件1.DispatcherServlet控制中心,控制其它组件执行,统一调度,降低组件之间的耦合性,提高每个组件的扩展性。2.HandlerMapping通过扩展处理器映射器实现不同的映射方式,例如:配置文件方式,实现接口方式,注解方式等。3.HandlAdapter通过扩展处理器适配器,支持更多类型的处理器;通过Handl

数据结构 将两个有序的链表合并为一个新链表_*^O^*—*^O^*的博客-程序员宝宝_数据结构实现两个链表的合并实例

问题描述将两个有序的链表合并为一个新链表,要求新的链表是通过拼接两个链表的节点来生成的,且合并后新链表依然有序。比如{1,4} {3,5},合并就是{1,3,4,5};解题思路首先我们要判定是否有一个链表为空,都为空,返回空,一个为空,则返回不为空的那个;其次找到,两个链表的第一个节点,比较小的那个,作为主链(head),将另一个的节点元素,依次比较,并入其中,最后肯定有一个链表先走完,那么只需要把未走完后续链表并入就好了。代码展示 public ListNode mergeTwoLists

win7安装python3.7_解决win7操作系统Python3.7.1安装后启动提示缺少.dll文件问题_weixin_39970064的博客-程序员宝宝

错误提示图片首先,我的操作系统是win7旗舰版,安装Python3.7.1之后启动时,提示如图错误,网上比较多的是两种处理方法:(1)安装Windows补丁程序(2)安装VC redit.exe第一种方案我这边下载了KB3118401、KB2999226,但是双击安装的时候安装不了;第二种方案大家都推荐的是安装v++2015,也安装成功了,但是安装后仍然报错。然后看着网上的推荐时间都比较早,我这边...

基础生物知识_小木亘的博客-程序员宝宝

1.SNP2.CNV3.可变剪接(alternative splicing)4.Gene isoformsGene isoforms are mRNAs that are produced from the same locus but are different in their transcription start sites (TSSs), protein coding DNA sequences (CDSs) and/or untranslated regions (UTRs), pote

mybatis 二级缓存失效_mybatis的一级缓存、二级缓存的过期时间分析_啟潍的博客-程序员宝宝

对于mybatis的缓存,我们往往有这样两个疑问:一级缓存、二级缓存的过期时间是多少?后台是否有个线程在检测?针对这两个问题,见下面的分析:1、一级缓存无过期时间,只有生命周期(1)MyBatis在开启一个数据库会话时,会创建一个新的SqlSession对象,SqlSession对象中会有一个Executor对象,Executor对象中持有一个PerpetualCache对象,见下面代码。当会话结...

Linux中的进程管理_Warrior-K的博客-程序员宝宝

文章目录一、进程的定义二、进程查看命令1. ps 进程查看2. pgrep 进程过滤3. pidof 查看命令产生进程的id4. top 动态进程查看三、进程优先级1. 优先级范围2. 更改优先级3. 进程状态四、进程前后台调用一、进程的定义进程是程序运行时的形态进程是程序的一个副本,硬盘内容复制到内存后再运行进程和线程:把一个进程分为多个线程,可以让多核cpu对进程中的多个线程同时工作进程是资源调用的最小单位线程是进程的最小单位进程的状态:R (TASK_RUNNING) &nbsp;&