2120B.md (2619B)
1 Source: https://codeforces.com/problemset/problem/2120/B 2 3 B. Square Pool 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Aryan and Harshith are playing pool in universe AX120 on a fixed square pool table of side $s$ with pockets at its $4$ corners. The corners are situated at $(0,0)$, $(0,s)$, $(s,0)$, and $(s,s)$. In this game variation, $n$ identical balls are placed on the table with integral coordinates such that no ball lies on the edge or corner of the table. Then, they are all simultaneously shot at $10^{100}$ units/sec speed (only at $45$ degrees with the axes). 22 23 In universe AX120, balls and pockets are almost point-sized, and the collisions are elastic, i.e., the ball, on hitting any surface, bounces off at the same angle and with the same speed. 24 25  26 27 Harshith shot the balls, and he provided Aryan with the balls' positions and the angles at which he shot them. Help Aryan determine the number of balls potted into the pockets by Harshith. 28 29 It is guaranteed that multiple collisions do not occur at the same moment and position. 30 31 Input 32 33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows. 34 35 The first line of each test case contains two integers $n$ and $s$ ($1 \le n \le 10^3$, $2 \le s\le 10^9$) — the number of balls placed on the table and the side length of the square pool table. 36 37 The $i$-th of the next $n$ lines contains four integers $d_x$, $d_y$, $x_i$, and $y_i$ ($d_x,d_y \in \{-1, 1\}$, $0 \lt x_i, y_i \lt s$) — the direction vectors of the launch on the $X$-axis and $Y$-axis respectively, and the coordinates of the location where the $i$-th ball was placed. It is guaranteed that no two balls coincide at the initial moment. 38 39 It is also guaranteed that the sum of $n$ over all test cases does not exceed $10^3$. 40 41 Output 42 43 For each test case, print a single integer — the number of balls potted in that game. 44 45 Example 46 47 Input 48 49 ``` 50 2 51 52 1 2 53 54 1 1 1 1 55 56 5 4 57 58 1 -1 1 1 59 60 1 -1 2 2 61 62 -1 1 2 3 63 64 1 -1 1 3 65 66 -1 1 3 1 67 ``` 68 69 Output 70 71 ``` 72 1 73 3 74 ``` 75 76 Note 77 78 In the first test case, there is a single ball and it's shot directly towards the pocket at $(2, 2)$, thus potted. 79 80 In the second test case, the state progresses as 81 82 | | | | 83 | --- | --- | --- | 84 | | $\rightarrow$ | | 85 86 | | | | 87 | --- | --- | --- | 88 | | $\rightarrow$ | | 89 90 | | | | 91 | --- | --- | --- | 92 | | $\rightarrow$ | | 93 94 | | | | 95 | --- | --- | --- | 96 | | $\rightarrow$ | |