×

# TAPOINT - editorial

Author: Tuấn Anh Trần Đặng
Tester: Kamil Dębowski
Editorialist: Tuấn Anh Trần Đặng

Medium

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

# Author's/Tester's Solutions:

This question is marked "community wiki".

116613
accept rate: 0%

19.8k350498541

 0 The bad side of this question was that someone could have just iterated 10^6 times from $x=R-1$ to $x=R-1-10^6$ so 10^6 * 100 test cases suffices in time, and get solution accepted. Nice maths though :D answered 19 Sep '16, 00:33 153●1●8 accept rate: 0%
 0 but the constraints were of the order 10^9 so this could TLE .... answered 19 Sep '16, 01:15 171●6 accept rate: 0%
 0 This problem can also be done by some sort of dfs. Start form $(R,0)$ and move one point left(to $(R-1,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$. my solution answered 03 Jan '17, 20:13 1.1k●2●11 accept rate: 10%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×2,657
×890
×647
×42
×6

question asked: 18 Sep '16, 15:50

question was seen: 2,648 times

last updated: 03 Jan '17, 20:15