BOJ 9735 - 삼차 방정식 풀기

BOJ 9735 - 삼차 방정식 풀기

이 문제가 화나는 이유는 고등수학에서 흔히 배우는 삼차방정식의 해를 찾는 방법으로 실수오차때문인지 이상한 체커때문인지 제대로 통과가 될 확률이 높지 않다는 것이다.

최대한 프로그래밍적으로 접근해서 실수오차를 제거해야하는데 그 방법은 다음과 같다.

친절하게 문제에서 정수해가 하나 있다고 하는게 힌트이다.

그리고 정수해가 $-10^6 \sim 10^6$ 이므로 이 범위를 모두 검사해서 정수해 하나를 찾고 조립제법을 시행한다.

그 해를 $x_1$ 이라 하면그럼 인수분해가 된 다음에는

$$ (x-x_1)(ax^2+(b+ax_1)x+((b+ax_1)x_1+c)) $$

이 된다.

이제 뒤 부분을 이차방정식의 판별식 $D=b^2-4ac$ 를 이용해 해를 찾아주면 된다.

해끼리 오차가 $10^{-4}$ 이하라면 중복제거를 해주고 정렬해서 출력해줘야 함에 유의한다.

#define double long double
const double eps = 1e-4;
void solve() {
   int a, b, c, d;
   cin >> a >> b >> c >> d;
   if (a < 0) a *= -1, b *= -1, c *= -1, d *= -1;

   auto fd = [&](double x) {
      return a * x * x * x + b * x * x + c * x + d;
   };

   int x1 = 0;
   for (int i = -1000000; i <= 1000000; i++) {
      if (fd(i) == 0) {
         x1 = i;
         break;
      }
   }
   b = b + a * x1;
   c = c + b * x1;

   int D = b * b - 4 * a * c;

   auto print = [&](vector<double> v) {
      sort(all(v));
      vector<double> v2;
      for (int i = 0; i < sz(v); i++) {
         if (!sz(v2) || v[i] - v2.back() > eps) v2.pb(v[i]);
      }
      cout.precision(9);
      for (double x: v2) cout << fixed << x << ' ';
      cout << endl;
   };

   if (D < 0) {
      print({(double) x1});
   } else if (D == 0) {
      double x2 = (double) -b / (2 * a);
      print({x2, (double) x1});
   } else {
      double x2 = ((double) -b - sqrt(D)) / (2 * a);
      double x3 = ((double) -b + sqrt(D)) / (2 * a);
      print({(double) x1, x2, x3});
   }
}