์๊ฐ ์ ํ | ๋ฉ๋ชจ๋ฆฌ ์ ํ | ์ ์ถ | ์ ๋ต | ๋งํ ์ฌ๋ | ์ ๋ต ๋น์จ |
---|---|---|---|---|---|
1 ์ด | 1024 MB | 69 | 31 | 27 | 60.000% |
๐ต๋๊ฐ ์ซ์ด ์ซ์ด ๋๋ฌด ์ซ์ด ์ซ์ด ์ค์ง๋ง ๋ด๊ฒ ์ฐ์ฉ๋์ง๋ง๐ต - ์ ์, ๋ชจ๊ธฐ์ก ไธญ
์ด๋ ๋ ์๋ฏผ์ด๋ ์์ ์ ๋ฐฉ ์ฐฝ๋ฌธ ๋ฐฉ์ถฉ๋ง์ ๊ตฌ๋ฉ์ด ๋ซ๋ ค์๋ค๋ ์ฌ์ค์ ์๊ฒ ๋์๋ค. ๋ชจ๊ธฐ๊ฐ ๋ฐฉ์ ๋ค์ด์ค๋ ๊ฒ ์ซ์ ์๋ฏผ์ด๋ ๋ฐฉ์ถฉ๋ง์ ๋ณด์ํ๋ ค๊ณ ํ๋ค. ํ์ง๋ง ์๋ฏผ์ด๋ ํ๋์ ๋ฐฉ์ถฉ๋ง ๋ณด์ ์คํฐ์ปค๋ง ๊ฐ๊ณ ์๋ค. ๋ฐฉ์ถฉ๋ง ๋ณด์ ์คํฐ์ปค๋ ๊ฐ๋ก์ ์ธ๋ก์ ๊ธธ์ด๊ฐ ๊ฐ์ ์ ์ฌ๊ฐํ์ด๋ค. ์๋ฏผ์ด๋ ์ด ํ ์ฅ์ ์คํฐ์ปค๋ก ์ต๋ํ ๋ง์ ๊ตฌ๋ฉ์ ๋นํ์์ด ๊ฐ๋ฆฌ๊ณ ์ถ์ด ํ๋ค.
์๋ฅผ ๋ค์ด ๊ตต์ ํ ๋๋ฆฌ์ ์ง์ฌ๊ฐํ๋ค์ ๊ตฌ๋ฉ์ด ๋ซ๋ ค์๋ค๊ณ ํ์. ๋นจ๊ฐ์ ์ ์ฌ๊ฐํ ํฌ๊ธฐ์ ๋ฐฉ์ถฉ๋ง ๋ณด์ ์คํฐ์ปค๊ฐ ์์ ๋ ๋นํ์์ด ์ต๋๋ก ๋ง์ ์ ์๋ ๊ตฌ๋ฉ์ 4๊ฐ๊ฐ ๋๋ค. ๋นํ์์ด ์ต๋ํ ๋ง์ ๊ตฌ๋ฉ์ ๋ง์ ์ ์๋ ๋ฐฉ์ถฉ๋ง ๋ณด์ ์คํฐ์ปค์ ์์น๋ ์ ์ผํ์ง ์์ ์ ์๋ค.
๋ฐฉ์ถฉ๋ง ๋ณด์ ์คํฐ์ปค๋ฅผ ์ ๋ถ์์ ๋ ๋นํ์์ด ์ต๋๋ก ๋ง์ ์ ์๋ ๊ตฌ๋ฉ์ ๊ฐ์๋ฅผ ์์๋ณด์.
์ฒซ์งธ ์ค์ ๋ฐฉ์ถฉ๋ง ๋ณด์ ์คํฐ์ปค์ ํ ๋ณ์ ๊ธธ์ด L์ด ์ฃผ์ด์ง๋ค. L์ ์ ์์ด๋ค. (1 ≤ L ≤ 1,000,000)
๋์งธ ์ค์ ๊ตฌ๋ฉ์ ๊ฐ์ K๊ฐ ์ฃผ์ด์ง๋ค. (1 ≤ K ≤ 100,000)
๋ค์ K๊ฐ์ ์ค์ ๊ตฌ๋ฉ์ ์์น ์ขํ (y1, x1, y2, x2)๊ฐ ํ ์ค์ ํ๋์ฉ ์ฃผ์ด์ง๋ค. (0 ≤ y1 < y2 ≤ 1,000,000, 0 ≤ x1 < x2 ≤ 1,000,000)
(y1, x1, y2, x2)๋ฅผ (y1, x1)์ ๊ตฌ๋ฉ์ ์ผ์ชฝ ์๋ ์ขํ, (y2, x2)์ ๊ตฌ๋ฉ์ ์ค๋ฅธ์ชฝ ์ ์ขํ๋ก ์ ์ํ๋ค. ์ฃผ์ด์ง๋ ์ขํ๋ ๋ชจ๋ ์ ์์ด๋ค.
๊ตฌ๋ฉ์ ์ผ๋ถ ๋๋ ์ ์ฒด๊ฐ ๊ฒน์ณ์ ์กด์ฌํ์ง ์๋๋ค. ๋ํ ์ฐ์๋ ๊ตฌ๋ฉ์ ํ๋์ ๊ตฌ๋ฉ์ผ๋ก ๋ณด์ง ์๊ณ ๋ ๋ฆฝ๋ ๊ตฌ๋ฉ์ผ๋ก ๋ณธ๋ค.
์ฒซ์งธ ์ค์ ๋ฐฉ์ถฉ๋ง ๋ณด์ ์คํฐ์ปค๋ก ๋นํ์์ด ๋ง์ ์ ์๋ ๊ตฌ๋ฉ์ ์ต๋ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค.
6 7 1 1 3 4 3 4 5 8 7 3 9 5 7 6 8 8 9 6 13 8 10 3 12 4 12 2 14 4
4
๋ณธ๋ฌธ์ ๊ทธ๋ฆผ์ ์ฐธ๊ณ ํ์