[BOJ C++] 백준 31529번: 2024년에는 혼자가 아니길

 📚 문제

[BOJ C++] 백준 31529번: 2024년에는 혼자가 아니길
https://www.acmicpc.net/problem/31529

 

 

 

---

 📝 입력 및 출력

 

---

 🔎 문제 풀이

MatKor intersection을 원점이라 하고 각 점을 x축, y축 위에 있다고 생각한다.
원점에서 A, B, C, D까지의 거리를 각각 a, b, c, d라고 하자.

피타고라스 정리에 의해 $\overline{AC}^2 = a^2 + c^2, \overline{BD}^2 = b^2 + d^2$이다.

• $X = \overline{AC}^2 + \overline{BD}^2 = a^2+c^2+b^2+d^2$
• $Y = \overline{AB}^2 + \overline{CD}^2 = (a+b)^2+(c+d)^2$$= X+2(ab+cd)$
• $= a^2+2ab+b^2+c^2+2cd+d^2$

따라서 $ab+cd = \frac {Y-X}2$이다.

또한, $\overline{OM} = (a-\frac{a+b}2)$, $\overline{ON} = (c-\frac{c+d}2)$ 이므로

(a>b, c>d를 가정한다. 크기가 반대인 경우에는 식이 조금 달라지지만, 아래에서 어차피 제곱하기 때문에 같은 결과가 나타나는 것을 알 수 있다.)

$\overline{MN}^2 = \overline{OM}^2 + \overline{ON}^2$

$= (a-\frac{a+b}2)^2 + (c-\frac{c+d}2)^2$

$= (\frac a2 - \frac b2)^2 + (\frac c2 - \frac d2)^2$

$= \frac 14(a^2-2ab+b^2+c^2-2cd+d^2)$

$= \frac 14(X-2(ab+cd))$

$= \frac 14(X-2\times\frac {Y-X}2)$

$= \frac 14(X-Y+X)$

$= \frac 14(2X-Y) = W$ 이다.

그러나 $\overline{MN}^2$는 길이의 제곱이므로 음수가 될 수 없고,
a, b, c, d는 모두 양수이므로 X보다 Y가 크다. (Y = X + 2(ab+cd)이므로)

즉, $2X-Y>0$, $X\leq Y$ 이다.

---

 ⌨️ C++ 코드

#include <bits/stdc++.h>
using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int x, y, w;
    cin >> x >> y;
    w = (2 * x - y);
    if (w < 0 || x > y)
        cout << -1;
    else
        cout << 2024 * w / 4;
}

코드는 의외로 굉장히 간단한 편이다..! 앞에서 설명한 식을 잘 유도하는 것이 중요한 문제이다.