[백준] 23239 당근 밭 (C++)

23239번: 당근 밭

ICPC Seoul Regional 2021 예선 B번 문제이다. 현재 solved.ac 기준 난이도는 플래티넘 V이며 개인적으로 쉽지 않았던 문제이다.

 

 

마구간의 가로(w), 세로(h)의 길이가 주어지고, 말을 묶은 줄의 길이(L)이 주어질 때, 말이 먹을 수 있는 당근의 개수를 구하는 문제이다. 줄은 마구간의 왼쪽 아래 모서리(0,0)에 묶여 있다. 당근은 마구간을 제외한 (정수, 정수) 점들에 위치해 있다. 마구간의 테두리에는 당근이 없음을 주의해야한다.

 

---

풀이

문제를 푸는 방식은 생각보다 어렵지 않다... 그냥 잘 세면 된다....

근데 저는 잘 세는 게 매우 어려웠습니다...ㅠ

 

1. 중심각이 270도인 호 내부에 있는 당근의 개수를 구해준다.

2. 만약 줄(L)의 길이가 마구간의 세로길이(h) 보다 큰 경우 답에 초록 영역 내부의 당근 개수를 더해준다.

3. 만약 줄(L)의 길이가 마구간의 가로길이(w) 보다 큰 경우 답에 파란 영역 내부의 당근 개수를 더해준다.

4. 영역 2와 영역 3의 겹치는 부분(빨강)이 생긴다면 답에서 빨간 영역 내부의 당근 개수를 빼준다.

 

 

1,2,3번 영역의 당근의 개수는 can_eat 함수를 통해 구하였다.

can_eat 함수는 사분원의 반지름이 주어졌을 때, 사분원 내에 있는 당근의 개수를 구하는 함수이다.

반지름 위에 있는 점은 can_eat 함수에서 계산하지 않았습니다. (함수 밖에서 따로 더해주었다.)

따라서, 반지름이 5일 때 can_eat함수의 리턴 값은 15이다.

파란점만 count

 

 

4번 영역의 당근의 개수는 overlap함수를 통해 구하였다. overlap 함수는 겹치는 부분이 생겼을 때, 두 번 count한 당근의 개수를 구하는 함수이다.

 

 

can_eat 함수와 overlap 함수 모두 피타고라스 방정식을 이용하여 내부에 있는지 점이 원하는 영역 안에 있는지 확인하였다.

---

코드

#include <bits/stdc++.h>
#define endl '\n'
#define INF 9876543210
using namespace std;
using ll = long long;

ll w, h, l, ans = 0;

ll can_eat(ll r) {
    ll carrot = 0;
    ll j = r - 1;
    for (ll i = 1; i < r; i++) {
        while (i * i + j * j > r * r) j--;
        carrot += j;
    }
    return carrot;
}

ll overlap() {
    ll carrot = 0;
    ll j = l - h - 1;
    for (ll i = h + 1; i < l - w; i++) {
        while (((i - h) * (i - h) + j * j > (l - h) * (l - h)) \
            || ((j - w) * (j - w) + i * i > (l - w) * (l - w))) j--;
        carrot += (j - w);
    }
    return carrot;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> w >> h >> l;
    ans += (2 * l + 3 * can_eat(l));               // 1번 영역
    if (l > h) ans += can_eat(l - h) + l - h;      // 2번 영역
    if (l > w) ans += can_eat(l - w) + l - w;      // 3번 영역
    if (l - h > w && l - w > h) ans -= overlap();  // 4번 영역
    cout << ans << endl;

    return 0;
}