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

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

29159번: 케이크 두 개

코드

#include <iostream>
using namespace std;

typedef long long ll;

ll gcd(ll a, ll b)
{
	if (b == 0) return a;
	else return gcd(b, a % b);
}

int main()
{
	ll ax = 0, ay = 0, bx = 0, by =0, x, y, dy, dx, k;
	for (int i = 0; i < 4; i++)
	{
		cin >> x >> y;
		ax += x;
		ay += y;
	}

	for (int i = 0; i < 4; i++)
	{
		cin >> x >> y;
		bx += x;
		by += y;
	}

	dy = by - ay;
	dx = bx - ax;

	ll value = gcd(dx, dy);
	dy /= value;
	dx /= value;

	if (dx < 0)
	{
		dy *= -1;
		dx *= -1;
	}

	cout << dy;
	if (dx != 1) cout << "/" << dx;

	k = dx * by - dy * bx;
	dx *= 4;

	value = gcd(k, dx);
	k /= value;
	dx /= value;

	if (dx < 0)
	{
		k *= -1;
		dx *= -1;
	}

	cout << " " << k;
	if (dx!= 1) cout << "/" << dx;
	return 0;
}

 

코드 설명

계산 및 출력 과정에서 숫자의 값이 많이 커질 수 있으므로 정수형 변수는 long long 만을 사용했다. 첫 두 개의 반복문을 통해서는 입력되는 직사각형의 x좌표값,  y좌표값을 각각 더해준다. 중점 좌표를 정확히 구하기 위해서는 /4를 해야하는데 기울기의 경우에는 굳이 이 과정이 필요하지 않으므로 바로 나누기 과정 없이 dx, dy를 구한다. dx, dy의 최대공약수를 구하고 dx, dy를 최대공약수로 나눠 기약분수 꼴로 만든다. 기울기가 음수일 경우 분자에 -를 붙여 출력해야 하므로 dx가 음수일 경우에 dx, dy에 모두 -1을 곱한다. 이후 기울기 p를 출력하는데  dx가 1이라면 기울기가 정수라는 의미이므로 dx는 굳이 출력하지 않는다.

 

두 번째로 이제 q를 구한다. 이를 위해 아래 식을 이용한다.

y = dy/dx * x + p
(dx를 양변에 곱해서 분수꼴을 없앤다.)
dx * y = dy * x + dx * p
dx * p =dx * y - dy * x 
(dx를 양변에 나눠준다.)
p = (dx * y - dy * x) / dx

 

변수 k를 dx * p로 사용할 것이므로 dx * y - dy * x 의 값을 대입한다. 이때 x, y의 값은 앞에서 구했던 직사각형 하나의 x좌표값의 합, y좌표값의 합인데,  /4를 적용하지 않은 채 대입되었기 때문에 dx에는 *4를 해준다.

 

이후 k와 dx에 대해 최대공약수를 구하고 기약분수 꼴로 만들어 기울기를 출력했던 것과 같은 로직으로 출력한다. 

 

느낀 점

처음에 너무 어렵게 생각하고 풀었다가 틀렸던 문제다. 각 직사각형의 중점을 지나는 선분을 찾아야 한다는 아이디어 자체는 바로 떠올렸지만 숫자를 다루는 과정에서 몇 번 틀렸다.

 

이후 오히려 가볍게 생각하고 문제를 다시 풀었는데 통과했다. 코드 자체는 길지만 중복되는 부분이 꽤 있다. 코드를 더 깔끔하게 작성하고 싶었는데 지금은 명확한 아이디어가 떠오르지 않아 이 상태로 올린다. 

컴파일에러는 변수 관련해서 난 에러다.