codeforces-scrape

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

2074D.md (2255B)


      1 Source: https://codeforces.com/problemset/problem/2074/D
      2 
      3 D. Counting Points
      4 
      5 time limit per test
      6 
      7 2 seconds
      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 The pink soldiers drew $n$ circles with their center on the $x$-axis of the plane. Also, they have told that the sum of radii is exactly $m$$^{\text{∗}}$.
     22 
     23 Please find the number of integer points inside or on the border of at least one circle. Formally, the problem is defined as follows.
     24 
     25 You are given an integer sequence $x_1,x_2,\ldots,x_n$ and a positive integer sequence $r_1,r_2,\ldots,r_n$, where it is known that $\sum_{i=1}^n r_i = m$.
     26 
     27 You must count the number of integer pairs $(x,y)$ that satisfy the following condition.
     28 
     29 * There exists an index $i$ such that $(x-x_i)^2 + y^2 \le r_i^2$ ($1 \le i \le n$).
     30 
     31 $^{\text{∗}}$Is this information really useful? Don't ask me; I don't really know.
     32 
     33 Input
     34 
     35 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     36 
     37 The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le m \le 2\cdot 10^5$).
     38 
     39 The second line of each test case contains $x_1,x_2,\ldots,x_n$ — the centers of the circles ($-10^9 \le x_i \le 10^9$).
     40 
     41 The third line of each test case contains $r_1,r_2,\ldots,r_n$ — the radii of the circles ($1 \le r_i$, $\sum_{i=1}^n r_i = m$).
     42 
     43 It is guaranteed that the sum of $m$ over all test cases does not exceed $2\cdot 10^5$.
     44 
     45 Output
     46 
     47 For each test case, output the number of integer points satisfying the condition on a separate line.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 4
     55 
     56 2 3
     57 
     58 0 0
     59 
     60 1 2
     61 
     62 2 3
     63 
     64 0 2
     65 
     66 1 2
     67 
     68 3 3
     69 
     70 0 2 5
     71 
     72 1 1 1
     73 
     74 4 8
     75 
     76 0 5 10 15
     77 
     78 2 2 2 2
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 13
     85 16
     86 14
     87 52
     88 ```
     89 
     90 Note
     91 
     92 On the first test case, the circle with $r_1=1$ is completely inside the circle with $r_2=2$. Therefore, you only have to count the number of integer points inside the latter. There are $13$ integer points such that $x^2+y^2 \le 2^2$, so the answer is $13$.
     93 
     94 On the second test case, the circle with $r_1=1$ is not completely inside the circle with $r_2=2$. There are $3$ additional points that are inside the first circle but not inside the second circle, so the answer is $3+13=16$.