Background

As everyone knows, in modern warfare on Luanxi Star, air superiority is very important. For this reason, people developed drone technology. Unfortunately, because Luanxi Star’s algorithmic level and communication capability in every sense are far too backward, these drones can only use independent, foolproof combat modes. These modes contain no randomness, so the outcome of a foolproof drone air battle can almost always be predicted before it starts.

In short, the foolproof unmanned fighter formations of the |\| Country and the () Country, which are at war with each other on Luanxi Star, have encountered each other in the airspace at their shared border. Now the militaries of both countries hope you can predict the result of this air battle.

Background

As everyone knows, in modern warfare on Luanxi Star, air superiority is very important. For this reason, people developed drone technology. Unfortunately, because Luanxi Star’s algorithmic level and communication capability in every sense are far too backward, these drones can only use independent, foolproof combat modes. These modes contain no randomness, so the outcome of a foolproof drone air battle can almost always be predicted before it starts.

In short, the foolproof unmanned fighter formations of the |\| Country and the () Country, which are at war with each other on Luanxi Star, have encountered each other in the airspace at their shared border. Now the militaries of both countries hope you can predict the result of this air battle.

Problem Description

Airspace and time

Due to the mysterious physical laws of Luanxi Star, time and space on Luanxi Star are not continuous. If we consider the moment when the encounter begins as time step $1$, then for any time step $k\in \N$, at both the start and the end of this time step, an object (a drone or a missile) can only be at a position of the form $(x,y,z)\in\mathbb Z^3$ (i.e., an integer lattice point in the airspace).

Drones

Because the airspace is much larger than a drone, we can treat a drone as a point mass (although in reality they look very similar to ordinary airplanes on Earth).

Flight state

At each time step, the flight state of a drone can be described by the following three groups of parameters.

1. The coordinate at the current time step $\vec p=(x,y,z)\in\mathbb Z^3$.
2. The direction vector $\vec{d}$ at the current time step, with $\|\vec d\|=1$.
   • Here, $\|\vec{v}\|$ denotes the length of vector $\vec v$. Let $\vec{v}=(v_x,v_y,v_z)$, then $\|\vec{v}\|=\sqrt{v_x^2+v_y^2+v_z^2}$.
   • You can simply think of $\vec d$ as the direction the nose of the aircraft points to.
3. The lift-line direction $\vec u$ at the current time step, with $\|\vec u\|=1,\vec u\bot \vec d$.
   • You can simply think of $\vec u$ as the unit normal vector of the plane of the aircraft, pointing from the belly to the back.
   • Then $\vec d$ and $\vec u$ uniquely determine a “left-hand direction” $\vec l=\vec u\times \vec d$.

Flight performance

Loosely speaking, an airplane usually has three control axes: pitch, roll, and yaw. Pitching down (negative stick) and pitching up (positive stick) correspond to the aircraft nose going downward and upward (i.e., keeping $\vec l$ unchanged). Rolling is rotation around the flight direction axis (i.e., keeping $\vec d$ unchanged). Yawing turns the nose left or right (i.e., keeping $\vec u$ unchanged). Due to special design, these drones have no yaw axis and can only pitch and roll. It is easy to see that even with only pitch and roll, a drone can freely change $\vec d$ and $\vec u$ (while maintaining $\|\vec u\|=\|\vec d\|=1,\vec u\bot \vec d$).

The above pitch (positive stick or negative stick), roll operations, straight flight, and their combinations are collectively called “maneuvers”.

Because of differences in drone models, a drone’s flight performance can be described by the following three groups of parameters. For convenience, in this section, let the parameters before one maneuver be $\vec p=(x,y,z),\vec d,\vec u,\vec l$, and after one maneuver be $\vec p'=(x',y',z'),\vec d',\vec u',\vec l'$.

1. Positive-stick rate $\theta_u\in(\dfrac\pi4,\dfrac\pi2)$ and negative-stick rate $\theta_d\in(\dfrac\pi4,\dfrac \pi2)$.
   • If the drone performs only a positive-stick maneuver, then it must satisfy $\vec p=\vec p',\vec l=\vec l',\vec u\cdot \vec d'\ge 0$. The time cost is $\dfrac{\angle(\vec d,\vec d')}{\theta_u}$.
   • If the drone performs only a negative-stick maneuver, then it must satisfy $\vec p=\vec p',\vec l=\vec l',\vec u\cdot \vec d'\le 0$. The time cost is $\dfrac{\angle(\vec d,\vec d')}{\theta_d}$.
2. Roll rate $\gamma\in(\dfrac\pi4,\dfrac \pi 2)$.
   • If the drone performs only a roll maneuver, then it must satisfy $\vec p=\vec p',\vec d=\vec d'$. The time cost is $\dfrac{\angle(\vec u,\vec u')}{\gamma}$.
3. Maximum flight speed $v_{m}>0$.
   • If the drone performs only straight flight, then it must satisfy $\vec d=\vec d',\vec u=\vec u'$. The time cost is $\dfrac{\|\vec p'-\vec p\|}{v_m}$.

Legal movement

At each time step, if a drone can start from flight state $\vec p=(x,y,z),\vec d,\vec u,\vec l$ and perform maneuvers strictly in the order roll, pitch (positive-stick or negative-stick), and straight flight, reaching a new flight state $\vec p'=(x',y',z')\not=\vec p,\vec d',\vec u',\vec l'$ such that $\vec d'//(\vec p'-\vec p)$, and the sum of time costs of all maneuvers is at most $1$, then this is called one (drone) legal composite maneuver.

If a drone can, from $\vec p=(x,y,z),\vec d,\vec u,\vec l$, perform one legal composite maneuver to reach $\vec p'=(x',y',z')\not=\vec p,\vec d',\vec u',\vec l'$, and among all legal composite maneuvers that reach $\vec p''=\vec p',\vec d'',\vec u'',\vec l''$, this one has the minimum total time cost, then this is called a (drone) legal movement (or the movement is legal). In this case, the drone moves along a straight line from $\vec p$ to $\vec p'$. Unless stated otherwise, “movement” below is assumed (and should be) a legal movement.

Cobra maneuver

At each time step, regardless of the drone’s flight performance, a drone can always use the Cobra maneuver to change from flight state $\vec p=(x,y,z),\vec d,\vec u,\vec l$ to $\vec p'=\vec p,\vec d'=\vec u,\vec u'=-\vec d,\vec l'=\vec l$. Note that this maneuver is not considered a legal maneuver.

Other parameters

In addition, a drone has the following parameters.

1. Drone ID (abbreviated as “ID”).
   • It is guaranteed that any two drones have different IDs.
2. Faction (abbreviated as “faction”).
   • The faction must be either the |\| Country or the () Country, and they regard each other as enemies.

Crash

A drone crashes if and only if it meets at least one of the following conditions.

1. During the movement of some activated missile, its distance to that missile is not greater than the missile’s proximity detonation distance (see below).
2. After some missile finishes its movement, it is at the same position as that missile (so the missile directly hits the drone; same below).
3. During the drone’s movement, there exists at least one activated missile such that its distance to the drone is not greater than that missile’s proximity detonation distance.
4. After the drone finishes its movement, there exists at least one missile whose position coincides with it.
5. After the drone finishes its movement, there exists another drone at the same coordinate (so they collide and both crash).

After a drone crashes, it disappears immediately. After that, it will not launch missiles and will not cause other drones to crash. However, missiles already launched by it do not disappear or explode immediately.

In this case, we also say the drone is destroyed.

Air-to-air infrared guided missiles

Similarly, an air-to-air infrared guided missile (hereafter “missile”) can also be treated as a point mass, and its flight state and flight performance can be described as well.

Flight state

Because a missile has no notion of up/down/left/right, only the following two groups of parameters are needed to describe its flight state.

1. The coordinate at the current time step $\vec p=(x,y,z)\in\Z^3$.
2. The direction vector $\vec{d}$ at the current time step, with $\|\vec d\|=1$.
   • You can simply think of $\vec d$ as the direction the missile’s warhead points to.

Flight performance

Also because a missile has no notion of up/down/left/right, it has no pitch, roll, or yaw axes. Its ability to change $\vec d$ is the same in all directions, and the operation of changing only $\vec d$ is collectively called “yaw”. This and straight flight, and their combinations, are collectively called “maneuvers”.

Thus, a missile’s flight performance can be described by the following two groups of parameters. For convenience, in this section, let the parameters before one maneuver be $\vec p=(x,y,z),\vec d$, and after one maneuver be $\vec p'=(x',y',z'),\vec d'$.

1. Yaw rate $\theta_r\in(\dfrac\pi4,\dfrac\pi2)$.
   • If the missile performs only yaw, then it must satisfy $\vec p=\vec p'$. The time cost is $\dfrac{\angle(\vec d,\vec d')}{\theta_r}$.
2. Maximum flight speed $v_m>0$.
   • If the missile performs only straight flight, then it must satisfy $\vec d=\vec d'$. The time cost is $\dfrac{\|\vec p'-\vec p\|}{v_m}$.

Legal movement

At each time step, if a missile can start from flight state $\vec p=(x,y,z),\vec d$ and perform maneuvers strictly in the order yaw and straight flight, reaching a new flight state $\vec p'=(x',y',z')\not=\vec p,\vec d'$ such that $\vec d//(\vec p'-\vec p)$, and the sum of time costs of all maneuvers is at most $1$, then this is called one (missile) legal movement (or the movement is legal). In this case, the missile moves along a straight line from $\vec p$ to $\vec p'$. Unless stated otherwise, “movement” below is assumed (and should be) a legal movement.

Other parameters

In addition, a missile has the following parameters.

1. Safety distance $d_s>0$ and activation status.
   • Immediately after being launched, a missile is inactive.
   • At the end of each time step, if a missile is inactive and either the drone that launched it has already crashed, or its distance to the launching drone is greater than the safety distance $d_s$, then it becomes activated. After that it stays activated, and we say it is activated, or that it is an activated missile.
2. Proximity detonation distance $d_p>0$.
   • During each missile movement, when an activated missile is within distance $d_p$ of any drone (including the launching drone), the missile enters the proximity-detonatable state (see “Explosion, disappearance, and proximity-detonatable” below).
   • During each drone movement, if there exists a drone within distance $d_p$ of an activated missile, then the missile also enters the proximity-detonatable state.
3. Maximum lock angle $\beta_s\in(\dfrac\pi4,\dfrac\pi2)$.
   • At any time, a missile with flight state $\vec p=(x,y,z),\vec d$ and maximum lock angle can lock onto a drone at $\vec p'$ if and only if $\vec d\cdot(\vec p'-\vec p)>0$ and $\angle(\vec d,\vec p'-\vec p)\le \beta_s$.
   • In this case, we say the drone can be locked by the missile, or that it is within the missile’s lock range.
   • We call $\angle(\vec d,\vec p'-\vec p)$ the lock angle.
4. Guidance time $t_z>0$.
   • If a missile is launched at time step $k$, then by the end of time step $k+t_z$, if it has still not exploded, it disappears immediately (see “Explosion, disappearance, and proximity-detonatable”). In this case, we say the missile exceeds its guidance time.

Explosion, disappearance, and proximity-detonatable

A missile explodes and disappears immediately when all of the following conditions hold.

1. Before the missile movement starts, the missile is activated.
2. One of the following conditions holds.
   1. During this missile movement, there exists a drone at $\vec q$ such that $\min_{\lambda\in[0,1]}\|\lambda \vec p+(1-\lambda)\vec p'-\vec q\|\le d_p$, where $\vec p,\vec p'$ are the start and end points of this missile movement.
      • In this case, all such drones are destroyed by this missile. Also, a drone may be destroyed by multiple missiles simultaneously.
   2. During a drone movement, there exists a drone that moves from $\vec q$ to $\vec q'$, satisfying $\min_{\lambda\in[0,1]}\|\lambda \vec q+(1-\lambda)\vec q'-\vec p\|\le d_p$, where $\vec p$ is the missile’s current position.
      • In this case, all such drones are destroyed by this missile. Also, this missile may destroy multiple such drones simultaneously.

In this case, we say the missile is proximity-detonatable, or the missile enters the proximity-detonatable state.

A missile does not explode but disappears at the end of the current time step when it meets at least one of the following conditions.

1. The missile loses lock (see “Missile losing lock” below), and it was already activated at the start of the current time step.
2. The missile exceeds its guidance time.
3. The missile is inactive, and after the missile finishes its movement, its position coincides with a drone.
   • In this case, the drone is destroyed by this missile. Also, a drone may be destroyed by multiple missiles simultaneously.
4. The missile is inactive, and after a drone finishes its movement, this missile’s position coincides with a drone.
   • In this case, the drone is destroyed by this missile. Also, one missile may destroy multiple such drones simultaneously.

Drone vision, radar search, and missile lock

Drone vision

At any time, a drone with flight state $\vec p=(x,y,z),\vec d,\vec u,\vec l$ can spot a drone at $\vec p'=(x',y',z')$ if and only if $\vec d\cdot(\vec p'-\vec p)> 0$. In this case, we say the drone at $\vec p'$ is within the vision of the drone at $\vec p$.

Onboard radar search range

A drone’s onboard radar (hereafter “radar”) scan range can be described by the following two parameters.

1. Horizontal scan range $L_x\in\N^+$ and vertical scan range $H_y\in\N^+$.
   • At any time, a drone with flight state $\vec p=(x,y,z),\vec d,\vec u,\vec l$ and radar scan range $L_x,H_y$ can scan a drone at $\vec p'$ if and only if $\vec d\cdot(\vec p'-\vec p)>0$ and $\exist x,y,s.t.\ |x|\le L_x,|y|\le H_y$ and $[\vec p'-(\vec p+x\vec l+y\vec u)]//\vec d$.
   • That is, if we build a plane $\alpha=\alpha(\vec p;\vec l,\vec u)$ with $\vec p$ as the origin and $\vec l,\vec u$ as the $X,Y$ axes, then the projection $\vec r=P(\vec p';\alpha)$ of $\vec p'$ onto this plane should lie within $[-L_x,L_x]\times [-H_y,H_y]$.
   • In this case, we say the drone at $\vec p'$ is within the radar scan range of the drone at $\vec p$.

Missile losing lock

After a drone finishes its movement, if the missile’s chosen target has already crashed, or it cannot be locked by this missile, then we say the missile loses lock, or is in the lost-lock state.

After that it stays in the lost-lock state forever, regardless of whether the previously chosen drone later becomes lockable again.

Drone target selection strategy

At any time, a drone (hereafter “our drone”, same below) chooses a target drone according to the following strategy.

1. If there is no enemy-faction drone (hereafter “enemy drone”, same below) within our drone’s vision, then our drone has no selected target.
2. Otherwise, if the drone selected by our drone in the previous time step is still within our drone’s vision, then our drone keeps selecting that target.
3. Otherwise, if there exists at least one enemy drone within our drone’s radar scan range, then choose the one with the smallest distance to our drone. If the closest enemy drone is not unique, choose the one with the smallest ID.
4. Otherwise, for an enemy drone within vision at $\vec p'$, let $\alpha=\alpha(\vec p;\vec l,\vec u),\vec r=P(\vec p';\alpha)=(r_x,r_y)$, then choose the one minimizing $\min\{|r_x-L_x|,|r_x+L_x|\}+\min\{|r_y-H_y|,|r_y+H_y|\}$. If there are multiple minima, also choose the one with the smallest ID.

Flight strategy

Drone flight strategy

Suppose the drone’s flight state is $\vec p=(x,y,z),\vec d,\vec u,\vec l$, its maximum flight speed is $v_m$, and its radar scan range is $L_x,H_y$.

1. If the drone has a selected target at $\vec p'$.
   1. If the drone can legally move to some position such that the enemy drone’s current position $\vec p'$ is still within our drone’s vision, then the drone legally moves to a flight state $\vec q=(x_q,y_q,z_q),\vec d_q,\vec u_q,\vec l_q$ such that the enemy drone’s current position $\vec p'$ is still within our drone’s vision, and $\|\vec p'-\vec q\|$ is minimized.
      1. If there are multiple such positions, let $\alpha_q=\alpha(\vec q;\vec l_q,\vec u_q),\vec r_q=P(\vec p';\alpha_q)=(r_{qx},r_{qy})$. Prefer positions that make $\vec r_q=(r_{qx},r_{qy})\in[-L_x,L_x]\times [-H_y,H_y]$.
         1. If there are still multiple such positions, choose the one minimizing $\|\vec r_q\|=\sqrt{r_{qx}^2+r_{qy}^2}$.
         2. If there are still multiple such positions, choose the lexicographically smallest $\vec q$.
      2. If no such $\vec r_q$ exists, choose the position minimizing $\min\{|r_{qx}-L_x|,|r_{qx}+L_x|\}+\min\{|r_{qy}-H_y|,|r_{qy}+H_y|\}$.
         1. If there are still multiple such positions, choose the lexicographically smallest $\vec q$.
   2. Otherwise, the drone legally moves to some position $\vec q$ that minimizes $\|\vec q-\vec p-v_m\vec d\|$.
      1. If there are multiple such positions, choose the lexicographically smallest $\vec q$.
2. Otherwise, the drone performs the Cobra maneuver to change its flight state to $\vec p=(x,y,z),\vec u,-\vec d,\vec l$.

It is guaranteed that in case 1. above, the drone can always legally move to some position.

Missile flight strategy

Suppose the missile’s current flight state at this time step is $\vec p,\vec d$, and the selected enemy drone’s flight state is $\vec p',\vec d',\vec u',\vec l'$.

If the missile had not lost lock by the end of the previous time step, let $\vec q'$ be the position where the enemy drone will move to in the next time step according to its flight strategy.

If the missile can legally move to $\vec q'$, then it moves directly to $\vec q'$.

Otherwise, it legally moves to a position $\vec q$ such that the enemy drone’s post-movement position $\vec q'$ is within lock range, and $\|\vec q-\vec q'\|$ is minimized.

1. If there are multiple such $\vec q$, choose the one with the smallest lock angle after movement.
2. If there are still multiple possibilities, choose the lexicographically smallest $\vec q$.

If no such position exists, or if the missile had already lost lock by the end of the previous time step, then the missile legally moves to some position $\vec q$ that minimizes $\|\vec q-\vec p-v_m\vec d\|$.

It is guaranteed that the missile can always legally move to some position.

Rules for drones launching missiles

A drone with flight state $\vec p=(x,y,z),\vec d,\vec u,\vec l$ (hereafter “our drone”) launches a missile at the target drone (hereafter “enemy drone”) at $\vec p'$ selected by our drone according to the following rule.

At the start of each time step, if the selected enemy drone is already within our drone’s radar scan range, and there is currently no missile launched by our drone that has not exploded (or disappeared), then it launches an inactive missile with initial flight state $\vec p,\vec d=\dfrac{\vec p'-\vec p}{\|\vec p'-\vec p\|}$, and this missile selects the enemy drone.

Order of events within the same time step

1. All drones select targets and determine the flight strategy for this time step.
2. All drones that can launch missiles launch missiles.
3. All missiles determine their flight strategy and move; during this process, some drones may be destroyed.
4. All proximity-detonatable missiles explode and disappear.
5. All drones move according to the flight strategy determined in 1.; during this process, some drones may be destroyed.
6. All proximity-detonatable missiles explode and disappear.
7. All drones at the same position collide and crash.
8. All missiles that exceed guidance time, and lost-lock missiles that are activated, disappear.
9. All missiles that can be activated become activated.

Task

Given, at the beginning of the airspace (i.e., at the start of time step $1$), the flight performance and state of each drone, and the flight performance of missiles, assuming this air battle will last for $T$ time steps, the commanders of both sides want you to output, in time order, all important events that occur at each time step.

Input Format

The first line contains two positive integers $n,T$, indicating there are $2n$ drones in total, and we simulate the first $T$ time steps. Among them, the first $n$ drones belong to the |\| Country, and the last $n$ drones belong to the () Country.

Next are $2n$ groups of data. The $i$-th group describes the drone with ID $i$ and contains multiple lines.

In each group:

The first line contains three integers representing $\vec p\in\mathbb Z^3$. It is guaranteed that all $\vec p$ are pairwise distinct, and the absolute value of each coordinate does not exceed $100$.

The second line contains six integers representing the drone’s $\vec d,\vec u$ in order. It is guaranteed that $\vec d,\vec u\in S_v$.

• Here, $S_v=\{(1,0,0),(-1,0,0),(0,1,0),(0,-1,0),(0,0,1),(0,0,-1)\}$.

The third line contains six real numbers representing the drone’s $\theta_u,\theta_d,\gamma,v_m,L_x,H_y$ in order.

The fourth line contains five real numbers and one positive integer representing the missile’s $\theta_r,v_m,d_s,d_p,\beta_s,t_z$ in order.

Output Format

Output $T$ groups of data. The $i$-th group represents the important events that occur in time step $i$.

In each group:

The first line contains three non-negative integers $p_1,p_2,p_3$, representing the number of drones destroyed during the missile movement in this time step, the number of drones destroyed during the drone movement in this time step, and how many groups of drones crash in pairwise collisions due to sharing the same position at the end of this time step.

Next, output $p_1$ lines. Each line is in the form $id_0\ k\ id_1\ id_2\ \cdots\ id_k$, meaning the drone with ID $id_0$ is destroyed during the missile movement in this time step, and in this process, there are $k$ missiles that destroyed this drone, launched by drones with IDs $id_1,id_2,\cdots,id_k$.

To ensure uniqueness of output, within each of these $p_1$ lines, $id_1,\dots,id_k$ must be output in increasing order, and the lines must be ordered by increasing $id_0$.

Next, output $p_2$ lines. Each line is in the form $id_0\ k\ id_1\ id_2\ \cdots\ id_k$, meaning the drone with ID $id_0$ is destroyed during the drone movement in this time step, and in this process, there are $k$ missiles that destroyed this drone, launched by drones with IDs $id_1,id_2,\cdots,id_k$.

To ensure uniqueness of output, within each of these $p_2$ lines, $id_1,\dots,id_k$ must be output in increasing order, and the lines must be ordered by increasing $id_0$.

Next, output $p_3$ lines. Each line is in the form $k\ id_1\ id_2\ \dots id_k$, meaning that at the end of this time step, there are $k$ drones at the same position, and their IDs are $id_1,...,id_n$.

To ensure uniqueness of output, within each of these $p_3$ lines, $id_1,\dots,id_k$ must be output in increasing order, the lines must be ordered by increasing $id_1$, and each ID appears at most once.

1 1
0 0 0
1 0 0 0 0 1
1 1 1 4 1 1
1 3 1 1 1 1
8 0 0
-1 0 0 0 0 1
1 1 1 4 1 1
1 3 1 1 1 1

0 0 1
2 1 2

1 4
0 0 0
1 0 0 0 0 1
1 1 1 3 1 1
1 15 3 2 1 10
60 0 0
-1 0 0 0 0 1
1 1 1 3 1 1
1 15 3 2 1 10

0 0 0
0 0 0
0 0 0
0 2 0
1 1 2
2 1 1

Hint

Sample Explanation 1

At time step $1$, two airplanes collide at $(4,0,0)$.

Sample Explanation 2

At time step $4$, two missiles destroy the enemy aircraft respectively.

Constraints

$T,n\le 100,3\le v_m\le 20$.

The total number of drones and missiles with $v_m>10$ does not exceed $10$.

$\theta_u,\theta_d,\gamma,\theta_r,\beta_s\in(\dfrac\pi4,\dfrac\pi2)$.

$1\le d_s,d_p\le 20,1\le t_z\le 100$.

$|x|,|y|,|z|\le 100$.

$1\le L_x,H_y\le 100$.

All real numbers in the input are precise to at most $6$ digits after the decimal point.

Initially, all $\vec p$ are pairwise distinct.

Source

From the 2023 Tsinghua University Programming Contest and Intercollegiate Invitational (THUPC2023) Preliminary Round.

Resources such as editorials can be found at https://github.com/THUSAAC/THUPC2023-Pre.

Translated by ChatGPT 5