[c++] BOJ 3108 :: ๋กœ๊ณ 
Algorithm ๋ฌธ์ œ/BOJ 2021. 8. 31. 21:01

๋ฌธ์ œ ๋กœ๊ณ ๋Š” ์ฃผ๋กœ ๊ต์œก์šฉ์— ์“ฐ์ด๋Š” ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์–ธ์–ด์ด๋‹ค. ๋กœ๊ณ ์˜ ๊ฐ€์žฅ ํฐ ํŠน์ง•์€ ๊ฑฐ๋ถ์ด ๋กœ๋ด‡์ธ๋ฐ, ์‚ฌ์šฉ์ž๋Š” ์ด ๊ฑฐ๋ถ์ด ๋กœ๋ด‡์„ ์›€์ง์ด๋Š” ๋ช…๋ น์„ ์ž…๋ ฅํ•ด ํ™”๋ฉด์— ๋„ํ˜•์„ ๊ทธ๋ฆด ์ˆ˜ ์žˆ๋‹ค. ๊ฑฐ๋ถ์ด๋Š” ์œ„์น˜์™€ ๊ฐ๋„๋กœ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค. ๊ฑฐ๋ถ์ด๋Š” ์ž…์— ์—ฐํ•„์„ ๋ฌผ๊ณ  ์žˆ๋Š”๋ฐ, ์—ฐํ•„์„ ๋‚ด๋ฆฌ๋ฉด ์›€์ง์ผ ๋•Œ ํ™”๋ฉด์— ์„ ์„ ๊ทธ๋ฆฌ๊ณ , ์˜ฌ๋ฆฌ๋ฉด ์„ ์„ ๊ทธ๋ฆฌ์ง€ ์•Š๊ณ  ๊ทธ๋ƒฅ ์ง€๋‚˜๊ฐ€๊ธฐ๋งŒ ํ•œ๋‹ค. ์ œ์ผ ์ฒ˜์Œ์— ๊ฑฐ๋ถ์ด๋Š” (0,0)์— ์žˆ๊ณ , ๊ฑฐ๋ถ์ด๊ฐ€ ๋ณด๊ณ  ์žˆ๋Š” ๋ฐฉํ–ฅ์€ y์ถ•์ด ์ฆ๊ฐ€ํ•˜๋Š” ๋ฐฉํ–ฅ์ด๋‹ค. ๋˜ํ•œ ์—ฐํ•„์€ ๋‚ด๋ฆฌ๊ณ  ์žˆ๋‹ค. ์‚ฌ์šฉ์ž๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๋‹ค์„ฏ๊ฐ€์ง€ ๋ช…๋ น์œผ๋กœ ๊ฑฐ๋ถ์ด๋ฅผ ์กฐ์ •ํ•  ์ˆ˜ ์žˆ๋‹ค. FD x: ๊ฑฐ๋ถ์ด๋ฅผ x๋งŒํผ ์•ž์œผ๋กœ ์ „์ง„ LT a: ๊ฑฐ๋ถ์ด๋ฅผ ๋ฐ˜์‹œ๊ณ„ ๋ฐฉํ–ฅ์œผ๋กœ a๋„ ๋งŒํผ ํšŒ์ „ RT a: ๊ฑฐ๋ถ์ด๋ฅผ ์‹œ๊ณ„ ๋ฐฉํ–ฅ์œผ๋กœ a๋„ ๋งŒํผ ํšŒ์ „ PU: ์—ฐํ•„์„ ์˜ฌ๋ฆฐ๋‹ค PD: ์—ฐํ•„์„..