HackerRank Geometry – Circle City

Challenge: Circle City

Scor cont: 30.0 / 30

Submission status: Accepted

Submission score: 1.0

Submission ID: 464734298

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/circle-city/problem

Cerinta

Roy lives in a city that is circular in shape on a $2D$ plane that has radius $r$. The city center is located at origin $(0,0)$ and it has suburbs lying on the lattice points (points with integer coordinates). The city Police Department Headquarters can only protect those suburbs which are located strictly inside the city. The suburbs located on the border of the city are still unprotected. So the police department decides to build at most $k$ additional police stations at some suburbs. Each of these police stations can protect the suburb it is located in.

Given the *square of radius*, $d (=r^2)$, of the city, Roy has to determine if it is possible to protect all the suburbs.

**Input Format**  
The first line of input contains integer $t$; $t$ test cases follow.  
Each of the next $t$ lines contains two space-separated integers: $d$, *the square of the radius* of the city, and $k$, the maximum number of police stations the headquarters is willing to build.

**Constraints**  
$ 1 \le t \le 10^{3} $  
$ 1 \le d \le 2 \times 10^{9} $  
$ 0 \le k \le 2\times10^{9} $  

**Output Format**  
For each test case, print in a new line `possible` if it is possible to protect all the suburbs;, otherwise, print `impossible`.

**Sample Input**

    5
    1 3
    1 4
    4 4
    25 11
    25 12

**Sample Output**

    impossible
    possible
    possible
    impossible
    possible

**Explanation**  

- For $d = 1$, there are $4$ points on circumference - _[(0,1), (0,-1), (1,0), (-1,0)]_.
- For $d = 4$, there are $4$ points on circumference - _[(0,2), (0,-2), (2,0),(-2,0)]_.
- For $d = 25$, there are $12$ points on circumference - _[(0,5), (0,-5), (3,4), (-3,4), (3,-4), (-3,-4), (4,3), (-4,3), (4,-3), (-4,-3), (5,0), (-5,0)]_.

*Test Case #01:* There are $4$ suburbs on the border, while we are allowed to construct max $k = 3$ police stations.  
*Test Case #02:* We can cover all the $4$ suburbs as exactly $4$ stations are allowed.  
*Test Case #03:* We can cover all the $4$ suburbs as exactly $4$ stations are allowed.  
*Test Case #04:* It is impossible to cover $12$ suburbs, on the border, with $11$ police stations.  
*Test Case #05:* We can to cover all $12$ suburbs, on the border, with $12$ police stations.  

**Timelimits**  

Timelimits for this challenge are given [here](https://hr-assets.s3.amazonaws.com/7bb46cae_challenge_assets/checker_limits/3926/limits.json)

Cod sursa

// ==================================================
// Problem  :   Circle City
// Score    :   30 /30
// Language :   C++14
// ==================================================

#include <cstdio>
#include <cmath>
using namespace std;

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);

    int t;
    scanf("%d", &t);

    while (t--) {
        int d, k;
        scanf("%d %d", &d, &k);

        int r = sqrt(d);
        int latticePointCount = 0;

        for (int x = 0; x <= r; ++x) {
            int y = sqrt(d - x * x);

            if (x * x + y * y == d) {
                ++latticePointCount;
            }
        }

        latticePointCount *= 4; // 4 quadrants

        if (r * r == d) {
            // Points on X-axis and Y-axis already taken twice
            latticePointCount -= 4;
        }

        printf(k < latticePointCount ? "impossible\n" : "possible\n");
    }

    return 0;
}