BOJ 29159 : 케이크 두 개

• 문제 링크 : boj.kr/29159
• 난이도 : S3
• 태그 : 기하학, 정수론

29159번: 케이크 두 개

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

ll gcd(ll a, ll b)
{
    if (!b) return a;
    return gcd(b, a % b);
}

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

    pll ma, mb;
    ma = mb = {0,0};
    for(int i = 0; i < 4; i++) {
        int a, b;
        cin >> a >> b;
        ma.first += a;
        ma.second += b;
    }
    for(int i = 0; i < 4; i++) {
        int a, b;
        cin >> a >> b;
        mb.first += a;
        mb.second += b;
    }

    ll ca, cb;
    ca = mb.second - ma.second;
    cb = mb.first - ma.first;
    ll da, db;
    da = cb*ma.second - ca*ma.first;
    db = cb * 4;
    ll gcdc = gcd(ca, cb);
    ca /= gcdc;
    cb /= gcdc;
    ll gcdd = gcd(da, db);
    da /= gcdd;
    db /= gcdd;

    if(cb < 0) {
        ca *= -1;
        cb *= -1;
    }
    if(cb == 1) {
        cout << ca << " ";
    }
    else {
        cout << ca << "/" << cb << " ";
    }

    if(db < 0) {
        da *= -1;
        db *= -1;
    }
    if(db == 1) {
        cout << da << " ";
    }
    else {
        cout << da << "/" << db << " ";
    }

    return 0;
}

---

풀이

어떤 직사각형의 넓이를 반으로 나누는 직선은 반드시 직사각형의 중심을 지난다.

따라서 직선의 방정식은 두 직사각형의 중심을 지난다.

 

직사각형의 중심을 구하는 간단한 방법은 각 점의 평균을 내는 것이다.

하지만 이렇게 구할 경우, 값이 정수가 아니게 되어 주의가 필요하다.

정수로 다루기 위해 4로 나누지 않고 수식을 정리하자.

직사각형 A의 중심*4를 ma, 직사각형 B의 중심*4를 mb라고 하자.

기울기 c의 분자를 ca, 분모를 cb라고 할 때, $ca = mby-may, cb = mbx-mby$이다.

상수 d의 분자를 da, 분모를 db라고 할 때, $da = (cb * may - ca * max), db = cb * 4$이다.

 

각각의 분자 분모를 최대공약수로 나눠준 뒤, 값에 따라 알맞은 출력을 해준다.