HackerRank: Circle City
Roy lives in a city that is circular in shape on a 2D plane. 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 radius of the city, Roy has to determine if it is possible to protect all the suburbs.
https://eightnoteight.wordpress.com/2015/01/24/hackerrank-circle-city/
the problem is simply to find out how many lattice points(ie (int, int)) on a circle with radius in a 2D plane.
http://www.28im.com/cpp/a1580931.html
https://codepair.hackerrank.com/paper/Ls3o7Qrc?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
https://codepair.hackerrank.com/paper/76EuOhWC?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
Lattice Point
A point at the intersection of two or more grid lines in a point lattice.
Roy lives in a city that is circular in shape on a 2D plane. 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 radius of the city, Roy has to determine if it is possible to protect all the suburbs.
- For
d=1 , there are4 points on circumference - [(0,1), (0,-1), (1,0), (-1,0)]. - For
d=4 , there are4 points on circumference - [(0,2), (0,-2), (2,0),(-2,0)]. - For
d=25 , there are12 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)].
https://eightnoteight.wordpress.com/2015/01/24/hackerrank-circle-city/
the problem is simply to find out how many lattice points(ie (int, int)) on a circle with radius in a 2D plane.
def main():def ans(r2, k):count = 0for x in xrange(int(ceil(sqrt(r2)))):if sqrt(r2 - x*x).is_integer():count += 4if count > k:return 'impossible'return 'possible'for _ in xrange(int(raw_input())):print ans(*map(int, raw_input().split()))
http://www.28im.com/cpp/a1580931.html
https://codepair.hackerrank.com/paper/Ls3o7Qrc?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
https://codepair.hackerrank.com/paper/76EuOhWC?b=eyJyb2xlIjoiY2FuZGlkYXRlIiwibmFtZSI6ImplZmZlcnl5dWFuIiwiZW1haWwiOiJ5dWFueXVuLmtlbm55QGdtYWlsLmNvbSJ9
Lattice Point
A point at the intersection of two or more grid lines in a point lattice.
Points(places) in a lattice which are occupied by the constituents of that lattice(atoms or ions) are called lattice points.
https://www.math.ucdavis.edu/~latte/background/countingLecture/intro/intro/