[BOJ 34330] ๊ธˆ์˜ค๋ฆฌ ๐Ÿฆ†

View as PDF

Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 1G

Problem types
Allowed languages
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text

</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

There are no comments at the moment.