[THUPC 2023 初赛] 乱西星上的空战

佬头 · 2024-07-19 10:28:22 · 题解

Description

有人想要在乱西星上打飞机，因此可爱的无人机就被迫在那里互相攻击，而每架无人机都是一个独特的个体，所以他们的性能略有不同。

现在知道了每架无人机的性能以及初始状态和各自导弹的性能，希望你能预测这一空战的结果。~~学校里刚学空间向量，正好来巩固一下。~~

Solution

Subtask 1

所有无人机选定目标（在视野范围内）。
1. 上一时刻本机选择的无人机优先选定（若存在）；
2. 其次是处于本机雷达扫描范围内的敌机；
  - 雷达扫描范围，以本机 \vec p 为原点、\vec l 和 \vec u 为 X,Y 轴建一平面 \alpha，敌机 \vec p' 在 \alpha 上的投影 \vec r=(\vec p'-\vec p)-[\vec d\cdot(\vec p'-\vec p)]\vec d 落在 [-L_x,L_x]\times [-H_y,H_y] 中，即 \vert\vec r\cdot\vec l\vert\le L_x 且 \vert\vec r\cdot\vec u\vert\le H_y。
3. 最后是对视野内处于 \vec p' 的敌机，选取 \vert L_x-\vert\vec r\cdot\vec l\vert\vert+\vert H_y-\vert\vec r\cdot\vec u\vert\vert 最小的。\|\vec l\|=\|\vec d\|\|\vec u\|\sin\theta=1。
所有无人机确定当前时刻内的飞行策略。~~（事故多发路段）~~
1. 题目里说 v_m>10 的无人机和导弹总数不超过 10；
2. 题目里又说某一时刻开始和结束时，无人机或导弹只能在形如 (x,y,z)\in\mathbb Z^3 的位置上（显然无人机和导弹是减缓位移速度后到达整点的）。
  - 因此可以暴力枚举 [-v_m,v_m]\times[-v_m,v_m]\times[-v_m,v_m] 内的整点，根据题意选择飞行策略。其余的与无人机目标的选定基本类似。
  - 必须是合法位移或一次眼镜蛇机动。
  - 无人机的俯仰有正负杆之分，在进行合法位移时，俯，需要考虑负杆率；仰，需要考虑正杆率。（这里与导弹略有不同，需要判断正负杆）
  - 无人机合法位移必须严格按照滚转、俯仰和直线飞行的顺序。（可以证明此顺序下的位移才可以是最快的）
  - 设目标点为 \vec q，考虑到仅有滚转、俯仰，滚转后应保证 \vec d,\vec u,(\vec q-\vec p) 共面，即 \vec l\perp\vec d,\vec l\perp\vec u。设 \vec d,(\vec q-\vec p) 构成的平面的单位法向量为 \vec n~(\vec n\cdot\vec l\ge0,(\vec d\times(\vec q-\vec p))\parallel \vec n)，则俯仰角为 \angle(\vec q-\vec p,\vec d)，滚转角为 \angle(\vec n,\vec l)。
  - 用向量的叉乘求 \vec n 时，还要特判一下 \vec d\parallel(\vec q-\vec p)，此时 \vec d\times(\vec q-\vec p)=\vec0。
    Subtask 2
    
    所有能发射导弹的无人机发射导弹。
  - 一架无人机同一时刻仅有一颗导弹（发射在外或由无人机机载）。
  - 导弹初始方向向量由本机指向敌机，并非与本机方向 \vec d 一致。
  - 发射导弹时敌机应在雷达范围内，而非视野范围。
  - 发射后至导弹第一次确定飞行策略期间，导弹默认为未脱锁状态。
    Subtask 3
所有导弹确定飞行策略。设 \vec p,\vec p' 为导弹本次位移的起点和终点。
1. 已脱锁或不管怎么位移都会脱锁，按照 v_m\vec d 盲飞。
2. 直接合法位移到敌机目标位置 \vec q。
3. 合法位移到距敌机最近且锁定角较小的整点，同样可以暴力枚举。
  - 锁定角 \angle(\vec p'-\vec p,\vec q-\vec p') 可以通过反余弦来计算，即 \arccos(\cos\angle(\vec p'-\vec p,\vec q-\vec p'))。
  - 导弹仅有偏航率。
所有导弹位移。
1. 导弹已激活（炸不到本机）。所有位于 \vec q，且 \min_{\lambda\in[0,1]}\|\lambda\vec p+(1-\lambda)\vec p'-\vec q\|\le d_p 的无人机被摧毁，同时导弹立即消失。
  - 简而言之，就是无人机 P 与导弹位移路径 AB 的距离 d 满足 d\le d_p，需要分类讨论。
  - 导弹不分敌我，激活后靠近即摧毁。
2. 导弹未激活。与导弹位移后重合的无人机被摧毁，导弹在本时刻结束时消失。
  - 导弹不分敌我，未激活时重合即摧毁。
    Subtask 4
    
    所有可空爆的导弹爆炸并消失。在判断无人机被爆炸摧毁后即可让这些导弹立即消失。
    
    Subtask 5
    
    所有无人机位移。基本与导弹位移相似。
所有从 \vec q 位移到 \vec q'，且满足 \min_{\lambda\in[0,1]}\|\lambda \vec q+(1-\lambda)\vec q'-\vec p\|\le d_p（\vec p 为某激活导弹此时的位置）的无人机被摧毁，同时这些导弹立即消失。
所有位移后与某未激活导弹重合的无人机被摧毁，导弹在本时刻结束时消失。
Subtask 6

所有可空爆的导弹爆炸并消失。在判断所有无人机被爆炸摧毁后即可让这些导弹立即消失。

Subtask 7

所有位置相同的无人机发生碰撞并坠毁。套两重循环即可（当然本机与本机不算重合）。
- 此时还需要判断一下每个导弹的锁定情况（是否脱锁），即锁定角 \angle(\vec d,\vec q-\vec p)\le\beta_s。~~脱锁之后没有目标就盲飞。~~
  Subtask 8
  
  所有超过制导时长 t_z 和脱锁且已激活的导弹消失。
- 第 k 个时刻被发射的导弹会在第 k+t_z 个时刻结束消失。也就是说会生效 t_z+1 个时刻。
- 本时刻脱锁且上一时刻激活的导弹才会消失（本时刻导弹尚未统一激活），同样导弹也不能提前激活。
- 导弹位移和无人机位移过程中，部分未激活导弹在此时可以消失了。
- 脱锁意味着导弹失去目标，导弹脱锁后将永久性盲飞，不具有重新锁定的能力。
  Subtask 9
  
  所有可激活的导弹被激活。
- 激活意味着导弹炸不到本机，导弹激活后将永久性激活，因此会误伤本机。
- 本机被摧毁后，导弹是激活而不是消失，在脱锁之前，理论上还可以飞很久。
  Importance
  
  接下来就是这道题的特色之处了——疯一般的实数问题。
- 判断实数 a,b 相等需要留有一定误差，即 \vert a-b\vert\lt e（e 这里取 10^{-6}），不能直接判断相等。
- 同理，判断实数 a 为零也不能直接判断，需要用 \vert a\vert\lt e。
- 判断实数 a\lt b 需要用 a+e\le b；a\le b 需要用 a\lt b+e 等。
- 在求 \arccos(cos\angle(\vec a,\vec b)) 时，需要写成 \arccos(\min\{cos\angle(\vec a,\vec b),1\})，否则 printf 会返回 -1.#IND00，cout 会返回 nan。~~我真是太难了。~~
- 在求 \sqrt{a} 时，应写成 \sqrt{a+e}，特别是用勾股定理求点到线段的距离的时候，不然一样会返回 -1.#IND00 或 nan。
- 每一时刻结束时检查一下答案数组是否需要清空。

基本上这题只有无人机和导弹的重合可以用等号直接判断（因为是整点）。

Code

~~懒婆娘的裹脚布——又臭又长。~~

#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#define square(x) (x)*(x)
using namespace std;
const int N = 202;
const double eps = 1e-6;
int n, nn, t;
int read(){
    int x = 0;
    bool tf = 0;
    char a = getchar();
    while(a < '0' || '9' < a) a == '-'? tf = 1: 0, a = getchar();
    while('0' <= a && a <= '9') x = (x << 1) + (x << 3) + (a ^ 48), a = getchar();
    return tf? -x: x;
}
void write(int x){
    if(x > 9) write(x / 10);
    putchar(x % 10 | 48);
}
struct vec{
    double x, y, z;
    void input(){
        x = read(), y = read(), z = read();
    }
    vec(double _x, double _y, double _z){
        x = _x, y = _y, z = _z;
    }
    vec(){};
    bool operator !() const{ //零向量
        return abs(x) < eps && abs(y) < eps && abs(z) < eps;
    }
    vec operator +(const vec &a) const{
        return vec(x + a.x, y + a.y, z + a.z);
    }
    vec operator -() const{
        return vec(-x, -y, -z);
    }
    vec operator -(const vec &a) const{
        return vec(x - a.x, y - a.y, z - a.z);
    }
    double operator *(const vec &a) const{ //点乘
        return x * a.x + y * a.y + z * a.z;
    }
    vec operator *(const double &a) const{ //数乘
        return vec(x * a, y * a, z * a);
    }
    vec operator /(const double &a) const{
        return vec(x / a, y / a, z / a);
    }
    vec operator ^(const vec &a) const{ //叉乘
        return vec(y * a.z - z * a.y, z * a.x - x * a.z, x * a.y - y * a.x);
    }
    bool operator <(const vec &a) const{ //字典序
        if(x == a.x){
            if(y == a.y) return z < a.z;
            return y < a.y;
        }
        return x < a.x;
    }
    bool operator ==(const vec &a) const{
        return x == a.x && y == a.y && z == a.z;
    }
};
struct total{
    vec p, d, u, l, stra;
    vec mp, md;
    double su, sd, r, vm, lx, hy; //无人机
    double msr, mvm, mds, mdp, mbs, mtz; //导弹
    int aim = 0, maim, mt;
    bool alive = 1, missile = 1, aim_inrad, lock, activate, need_die;
    void input(){
        p.input(), d.input(), u.input();
        l = u ^ d;
        scanf("%lf%lf%lf%lf%lf%lf", &su, &sd, &r, &vm, &lx, &hy);
        scanf("%lf%lf%lf%lf%lf", &msr, &mvm, &mds, &mdp, &mbs), mtz = read();
    }
} p[N];
vector <int> ans1, ans2, ans3, v[N]; //v[i]{1:导弹位移时的导弹;2:无人机位移时的导弹;3:重合的无人机数}
bool dead[N], missile_dead[N]; //绝对坠毁,绝对消失
double length(vec x){ //长度
    return sqrt(square(x.x) + square(x.y) + square(x.z));
}
vec unit(vec x){ //与其同向的单位向量
    x = x / length(x);
    return x;
}
vec shadow(vec p, vec d){ //计算投影r
    return p - d * (d * p);
}
bool inradar(vec u, vec &l, vec &r, double &lx, double &hy){ //在无人机机载雷达搜索范围内
    return abs(r * l) < lx + eps && abs(r * u) < hy + eps;
}
double distance(vec u, vec l, vec &r, double &lx, double &hy){
    return abs(lx - abs(r * l)) + abs(hy - abs(r * u));
}
void UAV_Choose(){ //无人机选定目标
    for(int i = 1; i <= nn; ++ i)
        if(p[i].alive){
            int aim = p[i].aim;
            vec raim = shadow(p[aim].p - p[i].p, p[i].d);
            if(aim && p[aim].alive && (p[aim].p - p[i].p) * p[i].d >= eps){
                p[i].aim_inrad = inradar(p[i].u, p[i].l, raim, p[i].lx, p[i].hy);
                continue;
            }
            aim = 0;
            bool is_inradar = 0;
            for(int j = 1 + (i <= n) * n; j <= n + (i <= n) * n; ++ j)
                if(p[j].alive && (p[j].p - p[i].p) * p[i].d >= eps){
                    vec r = shadow(p[j].p - p[i].p, p[i].d);
                    if(is_inradar == inradar(p[i].u, p[i].l, r, p[i].lx, p[i].hy))
                        if(is_inradar){
                            if(length(p[i].p - p[aim].p) >= length(p[i].p - p[j].p) + eps) aim = j, raim = r;
                        }
                        else{
                            if(!aim || distance(p[i].u, p[i].l, raim, p[i].lx, p[i].hy) >= distance(p[i].u, p[i].l, r, p[i].lx, p[i].hy) + eps) aim = j, raim = r;
                        }
                    else if(!is_inradar) aim = j, raim = r, is_inradar = 1;
                }
            p[i].aim = aim;
            p[i].aim_inrad = is_inradar;
        }
}
double cos(vec x, vec y){
    return min(x * y / length(x) / length(y), 1.0);
}
bool UAV_Legal(vec direct, vec &d, vec &u, vec &l, double &r, double &su, double &sd, double &vm){ //无人机能否合法位移
    if(!(direct ^ d)) return length(direct) / vm < 1 + eps;
    if((direct ^ d) * l <= -eps) return acos(cos(d ^ direct, l)) / r + acos(cos(direct, d)) / ((d ^ (d ^ direct)) * direct < 0? sd: su) + length(direct) / vm < 1 + eps;
    return acos(cos(direct ^ d, l)) / r + acos(cos(direct, d)) / ((d ^ (direct ^ d)) * direct < 0? sd: su) + length(direct) / vm < 1 + eps;
}
void UAV_Fly(){ //无人机飞行策略
    for(int i = 1; i <= nn; ++ i)
        if(p[i].alive){
            if(!p[i].aim){
                p[i].stra = vec(0, 0, 0); //眼镜蛇机动
                continue;
            }
            vec cur = vec(0, 0, 0), dir;
            bool inview = 0;
            for(dir.x = -int(p[i].vm); dir.x <= p[i].vm; ++ dir.x)
                for(dir.y = -int(p[i].vm); dir.y <= p[i].vm; ++ dir.y)
                    for(dir.z = -int(p[i].vm); dir.z <= p[i].vm; ++ dir.z)
                        if(!!dir && UAV_Legal(dir, p[i].d, p[i].u, p[i].l, p[i].r, p[i].su, p[i].sd, p[i].vm))
                            if((p[p[i].aim].p - p[i].p - dir) * dir >= eps){
                                if(!inview){
                                    inview = 1, cur = dir;
                                    continue;
                                }
                                double d = length(p[p[i].aim].p - p[i].p - dir), dcur = length(p[p[i].aim].p - p[i].p - cur);
                                if(dcur >= d + eps) cur = dir;
                                else if(!(d - dcur)){
                                    vec r = shadow(p[p[i].aim].p - p[i].p - dir, unit(dir)), rcur = shadow(p[p[i].aim].p - p[i].p - cur, unit(cur));
                                    vec l = !(p[i].d ^ dir)? p[i].l: unit(p[i].d ^ dir), lcur = !(p[i].d ^ cur)? p[i].l: unit(p[i].d ^ cur);
                                    if(inradar(unit(cur ^ lcur), lcur, rcur, p[i].lx, p[i].hy)){
                                        if(inradar(unit(dir ^ l), l, r, p[i].lx, p[i].hy) && length(rcur) >= length(r) + eps) cur = dir;
                                    }
                                    else if(inradar(unit(dir ^ l), l, r, p[i].lx, p[i].hy)) cur = dir;
                                    else if(distance(unit(cur ^ lcur), lcur, rcur, p[i].lx, p[i].hy) >= distance(unit(dir ^ l), l, r, p[i].lx, p[i].hy) + eps) cur = dir;
                                }
                            }
                            else if(!cur || !inview && length(cur - (p[i].d * p[i].vm)) >= length(dir - (p[i].d * p[i].vm)) + eps) cur = dir;
            p[i].stra = cur;
        }
}
void Task1(){
    UAV_Choose();
    UAV_Fly();
}
void Task2(int &t){ //发射
    for(int i = 1; i <= nn; ++ i)
        if(p[i].alive && p[i].missile && p[i].aim_inrad){
          p[i].missile = 0;
          p[i].mp = p[i].p;
          p[i].md = unit(p[p[i].aim].p - p[i].p);
          p[i].maim = p[i].aim;
          p[i].lock = 1;
          p[i].activate = 0;
          p[i].need_die = 0;
          p[i].mt = t;
        }
}
bool missile_legal(vec direct, vec &d, double &sr, double &vm){ //导弹能否合法位移
    return acos(min(d * direct / length(direct), 1.0)) / sr + length(direct) / vm < 1 + eps;
}
bool inlock_range(vec p, vec &d, double &bs){ //无人机可以被锁定
    return p * d >= eps && acos(cos(p, d)) < bs + eps;
}
double distance1(vec &p, vec &a, vec b){ //点到线段的距离
    if((a - p) * (a - b) <= -eps) return length(a - p);
    if((b - p) * (b - a) <= -eps) return length(b - p);
    return sqrt(square(a - p) - square((a - p) * (a - b) / length(a - b)) + eps); //减法可能导致结果小于0
}
void Task34(){ //导弹飞行策略
    for(int i = 1; i <= nn; ++ i)
        if(!p[i].missile){
            vec cur = vec(0, 0, 0), q = p[p[i].maim].p + p[p[i].maim].stra - p[i].mp, dir;
            bool cur_lock = 0;
            if(p[i].lock && missile_legal(q, p[i].md, p[i].msr, p[i].mvm)) cur = q;
            else{
                for(dir.x = -int(p[i].mvm); dir.x <= p[i].mvm; ++ dir.x)
                    for(dir.y = -int(p[i].mvm); dir.y <= p[i].mvm; ++ dir.y)
                        for(dir.z = -int(p[i].mvm); dir.z <= p[i].mvm; ++ dir.z)
                            if(!!dir && missile_legal(dir, p[i].md, p[i].msr, p[i].mvm))
                                if(p[i].lock && inlock_range(q - dir, dir, p[i].mbs)){
                                    if(!cur_lock || length(q - cur) >= length(q - dir) + eps) cur = dir, cur_lock = 1;
                                    else if(abs(length(q - dir) - length(q - cur)) < eps && cos(q - dir, dir) >= cos(q - cur, cur) + eps) cur = dir;
                                }
                                else if(!cur || (!p[i].lock || !cur_lock) && length(cur - (p[i].md * p[i].mvm)) >= length(dir - (p[i].md * p[i].mvm)) + eps) cur = dir;
            }
            if(p[i].activate){ //位移过程
                bool bomb = 0;
                for(int j = 1; j <= nn; ++ j)
                    if(p[j].alive && p[i].mdp > distance1(p[j].p, p[i].mp, p[i].mp + cur) - eps){
                        if(!dead[j]) ans1.push_back(j), dead[j] = 1;
                        bomb = 1;
                        v[j].push_back(i);
                    }
                if(bomb) p[i].missile = 1; //立刻消失
            }
            else for(int j = 1; j <= nn; ++ j)
                if(p[j].alive && p[j].p == p[i].mp + cur){
                    if(!dead[j]) ans1.push_back(j), dead[j] = 1;
                    v[j].push_back(i);
                    p[i].need_die = 1; //后来消失
                }
            p[i].mp = p[i].mp + cur;
            p[i].md = unit(cur);
        }
    for(int i = 1; i <= nn; ++ i)
        if(p[i].alive && dead[i])
            p[i].alive = 0; //局部时间存活的处死
}
void Task56(){ //无人机飞行
    for(int i = 1; i <= nn; ++ i)
        if(p[i].alive){
            for(int j = 1; j <= nn; ++ j)
                if(!p[j].missile)
                    if(p[j].activate){
                        if(p[j].mdp > distance1(p[j].mp, p[i].p, p[i].p + p[i].stra) - eps){
                            if(p[i].alive) ans2.push_back(i), p[i].alive = 0;
                            v[i].push_back(j);
                            missile_dead[j] = 1;
                        }
                    }
                    else if(p[j].mp == p[i].p + p[i].stra){
                        if(p[i].alive) ans2.push_back(i), p[i].alive = 0;
                        v[i].push_back(j);
                        p[j].need_die = 1; //后来消失
                    }
            if(p[i].alive)
                if(!p[i].stra){
                    swap(p[i].d, p[i].u);
                    p[i].u = -p[i].u;
                }
                else{
                    p[i].p = p[i].p + p[i].stra;
                    if(!!(unit(p[i].stra) - p[i].d)){
                        if(p[i].l * (p[i].stra ^ p[i].d) >= eps) p[i].l = unit(p[i].stra ^ p[i].d);
                        else p[i].l = unit(p[i].d ^ p[i].stra);
                        p[i].d = unit(p[i].stra);
                        p[i].u = p[i].d ^ p[i].l;
                    }
                }
        }
    for(int i = 1; i <= nn; ++ i)
        if(!p[i].missile && missile_dead[i])
                p[i].missile = 1, missile_dead[i] = 0; //局部时间保存的爆炸
}
void Task7(){ //无人机碰撞坠毁
    for(int i = 1; i <= nn; ++ i)
        if(p[i].alive){
            for(int j = 1; j <= nn; ++ j)
                if(i != j && p[j].alive && p[i].p == p[j].p){
                    if(p[i].alive){
                        ans3.push_back(i);
                        v[i].push_back(i);
                        p[i].alive = 0;
                    }
                    v[i].push_back(j);
                    p[j].alive = 0;
                }
        if(!p[i].alive){
            sort(v[i].begin(), v[i].end());
            ans3.back() = v[i].front();
            v[ans3.back()] = v[i];
        }
    }
}
void Check_Lock(){ //检查脱锁
    for(int i = 1; i <= nn; ++ i)
        if(!p[p[i].maim].alive || !inlock_range(p[p[i].maim].p - p[i].mp, p[i].md, p[i].mbs))
            p[i].lock = 0;
}
void Task8(int &t){
    for(int i = 1; i <= nn; ++ i)
        if(!p[i].missile && (p[i].mt + p[i].mtz == t || p[i].need_die || p[i].activate && !p[i].lock))
            p[i].missile = 1;
}
void Task9(){
    for(int i = 1; i <= nn; ++ i)
        if(!p[i].missile && !p[i].activate && (!p[i].alive || length(p[i].p - p[i].mp) >= p[i].mds + eps))
            p[i].activate = 1;
}
void Output(){
    write(ans1.size()), putchar(' ');
    write(ans2.size()), putchar(' ');
    write(ans3.size()), putchar('\n');
    sort(ans1.begin(), ans1.end());
    for(int i: ans1){
        write(i), putchar(' ');
        write(v[i].size()), putchar(' ');
        sort(v[i].begin(), v[i].end());
        for(int j: v[i]) write(j), putchar(' ');
        putchar('\n');
    }
    ans1.clear();
    sort(ans2.begin(), ans2.end());
    for(int i: ans2){
        write(i), putchar(' ');
        write(v[i].size()), putchar(' ');
        sort(v[i].begin(), v[i].end());
        for(int j: v[i]) write(j), putchar(' ');
        putchar('\n');
    }
    ans2.clear();
    sort(ans3.begin(), ans3.end());
    for(int i: ans3){
        write(v[i].size()), putchar(' ');
        for(int j: v[i]) write(j), putchar(' ');
        putchar('\n');
    }
    ans3.clear();
}
int main(){
    nn = (n = read()) << 1, t = read();
    for(int i = 1; i <= nn; ++ i) p[i].input();
    for(int i = 1; i <= t; ++ i){
        Task1();
        Task2(i);
        Task34();
        Task56();
        Task7();
        Check_Lock();
        Task8(i);
        Task9();
        Output();
    }
    return 0;
}

调到第三天半夜（悲），但是跑得比较慢，不知道为啥。

[THUPC 2023 初赛] 乱西星上的空战

Description

Solution

Subtask 1

Subtask 2

Subtask 3

Subtask 4

Subtask 5

Subtask 6

Subtask 7

Subtask 8

Subtask 9

Importance

Code