C언어 분수 대소비교

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

26519번: 함수와 최소 스패닝 트리

위 문제를 풀다가 정밀도 이슈가 있다고 생각되어 구조체를 이용하여 분수를 구현하였습니다.

 

$$\frac{a}{b} < \frac{c}{d}$$

우리가 흔히 알고있는 공식을 이용하면 a*d < b*c로 판별할 수 있으나 각각의 변수는 안전하지만 곱하는 순간 오버플로우에 취약합니다.

 

예를 들어 $$\frac{3965}{19814} < \frac{4789}{23456}$$

구하기 위해서는

$$3965*23456 < 4789*19814$$

와 같이 수가 급격하게 커지게 됩니다. 분수를 기울기로 접근하자면 아래와 같은 그림으로 표현할 수 있습니다.

파랑색의 숫자는 식의 좌항을 표현한 것이고 초록색의 숫자는 우항을 변형하여 나온 숫자입니다.

$$\frac{4789}{23456} = \frac{3965 + 824}{19814 + 3642}$$

$$\frac{3965}{19814} < \frac{1}{5}\; and\; \frac{824}{3642} > \frac{1}{5} $$

 

위와 같이 기울기를 통해 대소비교가 가능하며 이점으로는 판별식에서 수가 급격하게 커지는 것을 어느정도 방지할 수 있습니다.

 

$$
\frac{a}{b} < \frac{c}{d}=
\begin{cases}
a<c, & \text{if b == d}\\
(a-c)*d<c*(b-d) & \text{else if b > d}\\
a*(d-b)<(c-a)*b & \text{else}
\end{cases}
$$

두 분수가 같은지도 응용하면 쉽게 구할 수 있습니다.

 

[코드]

typedef struct Fraction {
   ll numerator;    // 분자
   ll denominator;  // 분모

   bool operator < (Fraction rhs) const {
      if(denominator == rhs.denominator)
         return numerator < rhs.numerator;

      if(denominator > rhs.denominator) {
         return (numerator-rhs.numerator) * rhs.denominator < (denominator-rhs.denominator) * rhs.numerator;
      }
      return numerator * (rhs.denominator - denominator) < denominator * (rhs.numerator - numerator);
   }

} Fraction;