AT_masters2024_final_a Windy Drone Control (A)

Takahashi wants to operate a flying drone on a two-dimensional plane and visit $ N $ destinations in arbitrary order. Let $ x $ -axis be east-west and $ y $ -axis be north-south. The drone's flight area is a $ 2\cdot 10^5\times 2\cdot 10^5 $ square surrounded by four walls with $ x=-10^5,x=+10^5,y=-10^5,y=+10^5 $ . Furthermore, in addition to these outer walls, there can exist other walls inside. The drone has a state with position $ (x,y) $ and velocity $ (v_x,v_y) $ . The position and velocity are always integer values. Starting from an initial state of position $ (s_x,s_y) $ and velocity $ (0,0) $ , you can perform either of the following two types of operations each turn. 1. Acceleration: Specify an integer vector $ (a_x,a_y) $ to change the velocity of the drone from $ (v_x,v_y) $ to $ (v_x+a_x,v_y+a_y) $ . It must satisfy $ a_x^2+a_y^2\leq 500^2 $ . 2. Measurement: Specify a non-zero integer vector $ (b_x,b_y) $ and measure the distance from the current drone position $ (x,y) $ to the nearest wall in the $ (b_x,b_y) $ direction with uncertainty. It must satisfy $ b_x^2+b_y^2\leq 10^{10} $ . Extend a ray from the point $ (x, y) $ in the direction towards $ (b_x, b_y) $ (the ray passing through $ (x+b_x,y+b_y) $ ) and calculate the Euclidean distance $ d = \sqrt{(x-x')^2 + (y-y')^2} $ to the point $ (x', y') $ where it first intersects a wall. The resulting value is $ \mathrm{round}(d\times \alpha) $ , where $ \alpha $ is a value sampled from a normal distribution with mean $ 1 $ and standard deviation $ \delta $ , given as an input parameter. Resample $ \alpha $ if $ \alpha \leq 0 $ . If the ray passes through an endpoint of a wall, it is considered to have hit the wall. However, if the ray is parallel to a wall, it does not count as a hit. After an operation, the wind causes the drone's velocity to change slightly from $ (v_x, v_y) $ . Based on the input parameter $ \epsilon $ , two samples are drawn from a normal distribution with mean $ 0 $ and standard deviation $ \epsilon $ . After rounding these sampled values, they are denoted as $ (f_x, f_y) $ . The new velocity of the drone then becomes $ (v_x + f_x, v_y + f_y) $ . At the end of each turn, the current position is updated to $ (x+v_x, y+v_y) $ based on the velocity $ (v_x, v_y) $ at that moment. However, if the line segment connecting $ (x, y) $ and $ (x+v_x, y+v_y) $ intersects with a wall (including cases where the line segment and the wall are parallel), it is considered a collision with the wall, and the position update is not performed; instead, the velocity is reset to $ (0, 0) $ . It is guaranteed that the drone is not in contact with any wall in its initial state, and in the event of a collision, the drone returns to its position before the collision, ensuring that the drone does not begin moving while in contact with a wall. If there is no collision with a wall, it is checked whether any destination has been reached. A destination $ (p_x, p_y) $ , which has not yet been visited, is considered reached if the distance between the line segment connecting $ (x, y) $ and $ (x+v_x, y+v_y) $ and the destination point is 1000 or less. This distance is defined as the minimum distance between any point $ q $ on segment $ S $ and point $ p $ . You can perform up to 5000 turns of operation, and the operation is completed immediately upon visiting all destinations. ### Input & Output Format First, information is given from Standard Input in the following format. > $ N $ $ M $ $ \epsilon $ $ \delta $ $ s_x $ $ s_y $ $ p_{x,0} $ $ p_{y,0} $ $ \vdots $ $ p_{x,N-1} $ $ p_{y,N-1} $ $ l_{x,0} $ $ l_{y,0} $ $ r_{x,0} $ $ r_{y,0} $ $ \vdots $ $ l_{x,M-1} $ $ l_{y,M-1} $ $ r_{x,M-1} $ $ r_{y,M-1} $ - The number of destinations is fixed at $ N=10 $ in all problems. - The number of walls $ M $ excluding the perimeter satisfies $ 0\leq M\leq 10 $ . - $ (s_x,s_y) $ represents the initial position of the drone, satisfying $ -10^5< s_x,s_y< 10^5 $ . It is guaranteed that it is not on a wall, including the outer perimeter. - $ (p_{x,i},p_{y,i}) $ denotes the coordinates of the $ i $ -th destination, satisfying $ -10^5\leq p_{x,i},p_{y,i}\leq 10^5 $ . The destinations may be in contact with walls. For each destination, the distance to the initial position and/or other destinations is guaranteed to be at least $ 5000 $ . - The $ (l_{x,i},l_{y,i}) $ and $ (r_{x,i},r_{y,i}) $ represent the coordinates of the $ i $ -th wall endpoint and satisfy $ -10^5\leq l_{x,i},l_{y,i},r_{x,i},r_{y,i}\leq 10^5 $ . The wall has a positive length and is guaranteed to have no common part with any wall other than the perimeter. It is also guaranteed to have no more than one point in common with the outer perimeter. From these conditions, it is guaranteed that all points in the flight area are reachable without passing through the walls. After reading the above information, repeat the following process for a maximum of $ 5000 $ turns. For acceleration, output the acceleration vector $ (a_x,a_y) $ to Standard Output in the following format. > A $ a_x $ $ a_y $ For measurements, output the direction $ (b_x,b_y) $ to be measured to Standard Output in the following format. > S $ b_x $ $ b_y $ Only when performing a measurement, an integer value representing the measurement result is given in a single line from Standard Input. **The output must be followed by a new line, and you have to flush Standard Output.** Otherwise, the submission might be judged as TLE. Note that the judge program will not respond to queries after all destinations have been visited nor after $ 5000 $ queries have been completed, so waiting for a response may result in a TLE. At the end of the turn, information on the results of the drone's movement is given from Standard Input in the following format. > $ c $ $ h $ $ q_0 $ $ \cdots $ $ q_{h-1} $ The value $ c $ indicates whether or not it collided with a wall, with $ c=1 $ if it collided with a wall, and $ c=0 $ if it did not. No information about which wall it collided with is available. The value $ h $ represents the number of destinations visited for the first time this turn, and each $ q_i $ in the next line is the ID of the destination visited for the first time ( $ 0\leq q_i\leq N-1 $ ). If $ h=0 $ , the line with $ q_i $ is skipped instead of a blank line. #### Example $ t $ Output Input Prior information ``` 2 0 10.0 0.1 43722 -75332 79243 32532 44002 -77034 ``` 0 ``` A 150 -400 ``` ``` 0 0 ``` 1 ``` S 0 1 ``` ``` 168969 0 1 1 ``` $ \vdots $

N/A

N/A

### Scoring Starting with an initial score of $ 0 $ , the score changes each turn as follows. 1. Score is reduced by $ 2 $ . 2. If the drone hits a wall, the score is additionally reduced by $ 100 $ . If it hits multiple walls at once, the score is only reduced by $ 100 $ . 3. If there is a destination reached for the first time, the score increases by $ 1000 $ for each one. The score at the moment with the highest score up until either 5000 turns have elapsed or all destinations have been visited will be the score for the test case. If your submission produces an illegal output or exceeds the time limit for some test cases, the submission itself will be judged as WA or TLE , and the score of the submission will be zero. The sum of the highest scores obtained during the contest will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, they will be ranked in the same place regardless of the submission time. ### Input Generation Let $ \mathrm{rand}(L,U) $ be a function that generates a uniform random integer between $ L $ and $ U $ , inclusive. We describe the common parts of all the problems. Refer to the "Differences by Problem" section below for the parts specific to each problem. #### Generation of $ s $ Generate $ s_x=\mathrm{rand}(-99999,99999) $ and $ s_y=\mathrm{rand}(-99999,99999) $ . #### Generation of $ p_{x,i} $ $ p_{y,i} $ For each i, generate $ p_{x,i}=\mathrm{rand}(-100000,100000) $ and $ p_{y,i}=\mathrm{rand}(-100000,100000) $ . If there is a point in $ s $ or $ (p_{x,j}, p_{y,j}) $ with Euclidean distance less than 5000, we regenerate $ (p_{x,i},p_{y,i}) $ . #### Generation of walls For each $ i $ , generate walls as follows. First, generate $ l_{x,i}=\mathrm{rand}(-90000,90000) $ and $ l_{y,i}=\mathrm{rand}(-90000,90000) $ , then set $ r_{x,i}'=l_{x,i}+\mathrm{rand}(-100000,100000) $ and $ r_{y,i}'=l_{y,i}+\mathrm{rand}(-100000,100000) $ . If $ (l_{x,i},l_{y,i})=(r_{x,i}',r_{y,i}') $ , we regenerate the $ i $ -th wall. If $ r_{x,i}' $ is out of range ( $ r_{x,i}'