### PROBLEM LINK:

**Author:** Tuấn Anh Trần Đặng

**Tester:** Kamil Dębowski

**Editorialist:** Tuấn Anh Trần Đặng

### DIFFICULTY:

Medium

### PREREQUISITES:

Geometry, Math

# Problem

Given 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.

# Solution

We 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)**

# Proof

Let q = the integer part of sqrt(R^2 - (R-1)^2) = sqrt(2*R - 1). We need to proof that when R is large enough the following condition must be true:

- (R - k/100) ^ 2 < (q^2 + (R - 1)^2) < R^2.

The second part of the inequation is obvious so let’s focus on the first part:

- (R - k/100)^2 < q^2 + (R - 1)^2

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 (R-1)^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).