codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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  ![](https://espresso.codeforces.com/138ce7bac82674c9a6751e6b772e6f1ef70c54be.png) 
     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$ |  |