[BOJ 34330] ๊ธ์ค๋ฆฌ ๐ฆ
View as PDF
</p>
๊ธ์ค์ง์ ๋ช ๋ฌผ ๊ธ์ค๋ฆฌ๋ฅผ ๋ณด๊ธฐ ์ํด ์ํธ๋ ๊ธ์ค์ง ์ฐ๋ชป์ ๋ฐฉ๋ฌธํ๋ค.
๊ธ์ค๋ฆฌ๋ฅผ ๋๋ฌด ํค์ฐ๊ณ ์ถ์๋ ์ํธ๋ ๊ธ์ค๋ฆฌ๋ฅผ ์ต๋ํ ๋ง์ด ํฌํํ๋ ค ํ๋ค.
์ฐ๋ชป์ $(0, 0)$์ ์ค์ฌ์ผ๋ก ํ๋ ๋ฐ์ง๋ฆ $R$์ ์ ๋ชจ์์ด๊ณ , $N$๊ฐ์ ์ฐ๊ฝ์๊ณผ $M$๋ง๋ฆฌ์ ๊ธ์ค๋ฆฌ๊ฐ ์ฐ๋ชป์ ์๋ค. ์ฐ๊ฝ์์ ์, ๊ธ์ค๋ฆฌ๋ ์ ์ผ๋ก ํํ๋๋ฉฐ, ์์ ์ค์ฌ๊ณผ ์ ์ ๋ชจ๋ ์ฐ๋ชป์ ๋ด๋ถ ๋๋ ๊ฒฝ๊ณ ์์ ์๋ค.
์ํธ๋ ์ฐ๋ชป ๋ฐ๊นฅ๊ณผ ์ฐ๊ฝ์ ์์์ ์์ ๋กญ๊ฒ ์ด๋ํ ์ ์์ผ๋ฉฐ, ๊ฒน์ณ์๊ฑฐ๋ ๋ง๋ฟ์ ์๋ ์ฐ๊ฝ์์ ์ด์ฉํด ๋ค๋ฅธ ์ฐ๊ฝ์ ๋๋ ์ฐ๋ชป ๋ฐ๊นฅ์ผ๋ก ๊ฑด๋๋ค๋ ์ ์๋ค. ์ํธ์ ์ฒ์ ์์น๋ ์ฐ๋ชป ๋ฐ์ด๋ค.
์ํธ๋ ๊ธธ์ด $L$์ ๋ฐ์ฑ๋ฅผ ์ด์ฉํ์ฌ ์์ ์ด ์ ์๋ ์์น์์ ๊ฑฐ๋ฆฌ๊ฐ $L$ ์ดํ์ธ ๊ธ์ค๋ฆฌ๋ฅผ ์ํ๋ ๋งํผ ํฌํํ ์ ์๋ค. ์ํธ๋ ์ต๋ ๋ช ๋ง๋ฆฌ์ ๊ธ์ค๋ฆฌ๋ฅผ ํฌํํ ์ ์์๊น?
์ ๋ ฅ ํ์
์ฒซ์งธ ์ค์ ์ฐ๋ชป์ ๋ฐ์ง๋ฆ $R$, ๋ฐ์ฑ์ ๊ธธ์ด $L$์ด ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถ๋์ด ์ฃผ์ด์ง๋ค. $(1 \le R, L \le 10^9)$</p>
๋์งธ ์ค์๋ ์ฐ๊ฝ์์ ์ $N$, ๊ธ์ค๋ฆฌ์ ์ $M$์ด ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถ๋์ด ์ฃผ์ด์ง๋ค. $(0 \le N, M \le 100)$
์ด์ด์ $N$๊ฐ์ ์ค์ ๊ฑธ์ณ $x_i$, $y_i$, $r_i$๊ฐ ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถ๋์ด ์ฃผ์ด์ง๋ค. ์ด๋ $i$๋ฒ์งธ ์ฐ๊ฝ์์ด $(x_i,y_i)$๋ฅผ ์ค์ฌ์ผ๋ก ํ๋ ๋ฐ์ง๋ฆ $r_i$์ ์์์ ์๋ฏธํ๋ค. $(-10^9 \le x_i, y_i \le 10^9;$ $1\le r_i\le 10^9)$
์ด์ด์ $M$๊ฐ์ ์ค์ ๊ฑธ์ณ $x_j$, $y_j$๊ฐ ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถ๋์ด ์ฃผ์ด์ง๋ค. ์ด๋ $j$๋ฒ์งธ ๊ธ์ค๋ฆฌ์ ์์น๊ฐ $(x_j,y_j)$์์ ์๋ฏธํ๋ค. $(-10^9 \le x_j, y_j \le 10^9)$
์ฃผ์ด์ง๋ ๋ชจ๋ ์๋ ์ ์์ด๊ณ , ์ฃผ์ด์ง๋ ๋ชจ๋ ์ขํ๋ $(0,0)$๊ณผ ๊ฑฐ๋ฆฌ๊ฐ $R$ ์ดํ์์ด ๋ณด์ฅ๋๋ค.
์ถ๋ ฅ ํ์
ํฌํํ ์ ์๋ ๊ธ์ค๋ฆฌ ์์ ์ต๋๊ฐ์ ์ถ๋ ฅํ๋ค.
์์ ์ ๋ ฅ
100 1
1 2
0 -99 1
0 -97
0 99
์์ ์ถ๋ ฅ
2
Comments