BOJ 9735 : 삼차 방정식 풀기

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

9735번: 삼차 방정식 풀기

풀면서 욕 뒤지게 해먹은 문제

수학(상)에 나오는 3차방정식대로 풀 수 있다.

먼저 문제를 관찰하면 한개의 정수해는 존재하고, 정수해의 범위가 정해졌으니 그 정보를 이용해서 정수해를 찾는다.

정수해를 a라고 하면 방정식은 이런 형태를 띤다.

(x-a)(bx^2+cx+d)=0

이때 저 나머지 이차방정식은 판별식과 근의 공식을 사용하자.

나머지 신경써줘야 할 부분(해 오름차순으로 출력, 중근 처리)는 set을 통해 관리하자. 왜냐하면 set은 중복되는 원소를 걍 하나의 원소로 저장하고 항상 원소들을 정렬해놓기 때문이다.

 

실수 처리나 나머지 신경써줘야 할 부분에서 심한 뇌절이 오는 바람에 4시간을 삽질했다.

 

#include <bits/stdc++.h>
#define MEM 10009
#define sanic ios_base::sync_with_stdio(0)
#define pb push_back
using namespace std;
typedef long long ll;
typedef long double dou;
typedef pair<ll, ll> pii;
const ll MOD = 1e9+7;
ll t;
dou a,b,c,d;
ll D(dou p, dou q, dou r){
    dou ret=q*q-4*p*r;
    return ret;
}
int main()
{
    cin >> t;
    cout.precision(9);
    cout << fixed;
    while(t--){
        dou x;
        cin >> a >> b >> c >> d;
        for(dou i=0; i<=2000000; i+=1){
            if(a*i*i*i+b*i*i+c*i+d==0){
                x=i;
                break;
            }
            if(-a*i*i*i+b*i*i-c*i+d==0){
                x=-i;
                break;
            }
        }
        d = a*x*x+b*x+c;
        c = a*x+b;
        b = a;
        if(D(b,c,d)<0){
            cout << x << '\n';
        }
        else{
            set<dou> s;
            s.insert(x);
            s.insert((-c+sqrt(D(b,c,d)))/(2*b));
            s.insert((-c-sqrt(D(b,c,d)))/(2*b));
            for(set<dou>::iterator it=s.begin(); it!=s.end(); ++it)
                cout << *it << ' ';
            cout << '\n';
        }
    }
}

 이 코드를 배끼는 사람은 나의 4시간 삽질을 무시하였기(?) 때문에 진짜 각오하도록.