PROBLEM LINK:Author: Tuấn Anh Trần Đặng DIFFICULTY:Medium PREREQUISITES:Geometry, Math ProblemGiven a circle and a number K find one point that is with in the circle, not on the circle border and not further than K/100 from the circle border. SolutionWe need to find x and y such that (R  k/100)^2 <= x^2 + y^2 <= R^2. With small R we may try all possible values of x from 1 to R  1 and find y = the integer part of sqrt(R^2  x^2). The trick is if R is large enough you will find the solution with x = R  1. More specifically in this problem, if R is larger than 20000 then the solution would be x = R  1 and y = integer part of sqrt(R^2  x^2) ProofLet q = the integer part of sqrt(R^2  (R1)^2) = sqrt(2*R  1). We need to proof that when R is large enough the following condition must be true:
The second part of the inequation is obvious so let’s focus on the first part:
From the definition of q we have that: abs(q  sqrt(2*R  1)) <= 1 => q >= sqrt(2 * R  1)  1 => q^2 >= 2*R  1  2 * sqrt(2 * R  1) + 1 <=> q^2 >= 2 * R  2 * sqrt(2 * R  1) add (R1)^2 into both side of the inequations: q^2 + (R  1)^2 >= 2 * R  2 * sqrt(2 * R  1) + (R  1)^2 <=> q^2 + (R  1)^2 >= R^2  2 * sqrt(2*R  1) + 1. (1) With R is large enough it’s obvious to see that 2 * sqrt(2 * R  1) + 1< 2 * (k/100) * R + (k/100) ^ 2 (2). Finding how exactly would be the large enough value left as an exercise for you. From (1) and (2) we have: with R is large enough: q^2 + (R  1)^2 > R^2  2 * (k/100) * R + (k/100)^2 <=> q^2 + (R  1) ^ 2 > (R  k/100)^2 (this is what we need to prove). Author's/Tester's Solutions:
This question is marked "community wiki".
asked 18 Sep '16, 15:50

The bad side of this question was that someone could have just iterated 10^6 times from $x=R1$ to $x=R110^6$ so 10^6 * 100 test cases suffices in time, and get solution accepted. Nice maths though :D answered 19 Sep '16, 00:33

but the constraints were of the order 10^9 so this could TLE .... answered 19 Sep '16, 01:15

This problem can also be done by some sort of dfs. Start form $(R,0)$ and move one point left(to $(R1,0)$) and one point up(to $(R,1)$) and then keep moving like this for all points. $S=$ $\{$set of all points that satisfy the given conditions$\}$ Whichever point you reach check if that point can be the answer. Don't go further from point $P_{1}$, when you reach a point $P_{1}$ from which no point $P_{2} \in S$ can be reached. This should cover all points, and if no point satisfies the conditions then print $1$. answered 03 Jan '17, 20:13
