[백준 / BOJ] C++ 29159 케이크 두 개

29159번: 케이크 두 개

 

문제

https://www.acmicpc.net/problem/29159

29159번: 케이크 두 개

 

 

풀이

두 직사각형 각각의 중심 좌표를 구하고, 두 점을 지나는 일차방정식을 구하는 문제다. 분수 형태의 출력 형식 때문에 애를 먹은 문제다.

먼저 일차방정식의 형태를 보면 y - y1 = ((x2 - x1)/(y2 - y1))(x - x1)이다. y = Px + Q 형태로 나타냈을 때 P와 Q를 출력하는 문제다.

먼저 기울기 P = (x2 - x1) / (y2 - y1) 으로 나타낼 수 있다. Q는 P를 사용하면 Q = -P * x1 + y1으로 나타낼 수 있다.

 

직사각형의 중심 좌표는 ((x_a+x_b)/2,(y_a+y_b)/2) 형태로 표현될 수 있으므로 /2는 생략하고 변수에 저장했다. (나중에 약분을 해야 해서 정수형태를 유지하기 위함)

분자를 p, 분모를 q라고 했을 때 기울기 P는 p = x2 - x1, q = y2 - y1이 된다. x1, x2, y1, y2가 모두 /2를 생략하고 있으므로 무시해도 된다.

Q는 P를 이용해 출력하는데, Q = -P * x1 + y1 이므로 y1은 2라는 분모를 가지고 있고 P의 분모와 다를 수 있으므로 통분해서 하나의 분수로 나타내야한다. 따라서 Q의 p = -P * x1 * 2 + y1 * (P의 q), q = 2 * (P의 q)가 된다.

 

분모와 분자를 기약분수 형태로 출력해야하므로 유클리드 호제법 등으로 최대공약수를 구해 분모 분자를 나누면 된다. 단, 출력 시 음수 표현에 주의해야 하는데 분모 분자가 모두 음수인 경우 양수이기 때문에 둘 다 -1을 곱해줘야 한다. 그리고 분모가 음수인 경우에도 분모는 양수로, 분자는 음수로 바꾸기 위해 둘 다 -1을 곱해주면 된다. (즉, 분모가 음수인 경우 분자 분모에 모두 -1을 곱하기)

계산 시 32비트 정수 범위를 넘어갈 수 있기 때문에 long long을 사용해야한다.

(대회 중 풀어서 코드는 좀 많이 더럽다.)

 

 

코드

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

ll gcd(ll a, ll b) {
  return b ? gcd(b, a % b) : a;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int INF = INT_MAX;
  vector<pair<int, int>> v(4);
  int min_x = INF, min_y = INF, max_x = INF, max_y = INF;
  for (int i = 0; i < 4; i++) {
    cin >> v[i].first >> v[i].second;
    if (min_x == INF)
      min_x = v[i].first;
    else
      min_x = min(min_x, v[i].first);
    if (min_y == INF)
      min_y = v[i].second;
    else
      min_y = min(min_y, v[i].second);
    if (max_x == INF)
      max_x = v[i].first;
    else
      max_x = max(max_x, v[i].first);
    if (max_y == INF)
      max_y = v[i].second;
    else
      max_y = max(max_y, v[i].second);
  }
  ll x1 = max_x + min_x;
  ll y1 = max_y + min_y;
  min_x = INF, min_y = INF, max_x = INF, max_y = INF;
  for (int i = 0; i < 4; i++) {
    cin >> v[i].first >> v[i].second;
    if (min_x == INF)
      min_x = v[i].first;
    else
      min_x = min(min_x, v[i].first);
    if (min_y == INF)
      min_y = v[i].second;
    else
      min_y = min(min_y, v[i].second);
    if (max_x == INF)
      max_x = v[i].first;
    else
      max_x = max(max_x, v[i].first);
    if (max_y == INF)
      max_y = v[i].second;
    else
      max_y = max(max_y, v[i].second);
  }
  ll x2 = max_x + min_x;
  ll y2 = max_y + min_y;
  ll p = y2 - y1;
  ll q = x2 - x1;
  ll g = gcd(p, q);
  p /= g;
  q /= g;
  if (p < 0 && q < 0) {
    p *= -1;
    q *= -1;
  } else if (p > 0 && q < 0) {
    p *= -1;
    q *= -1;
  }
  if (q == 1) {
    cout << p << ' ';
  } else {
    cout << p << '/' << q << ' ';
  }
  p = p * -x1 + y1 * q;
  q *= 2;
  g = gcd(p, q);
  p /= g;
  q /= g;
  if (p < 0 && q < 0) {
    p *= -1;
    q *= -1;
  } else if (p > 0 && q < 0) {
    p *= -1;
    q *= -1;
  }
  if (q == 1) {
    cout << p;
  } else {
    cout << p << '/' << q;
  }
  return 0;
}