Cod sursa(job #1743371)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 18 august 2016 02:12:40
Problema Ecuatie Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <fstream>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

ifstream cin("ecuatie.in");
ofstream cout("ecuatie.out");

int nd = 0, d[20005];
long long a, b, c;

struct answer {
    int p1, p2, q1, q2;
    answer() {}
    answer(int p1, int q1, int p2, int q2) {
        this->p1 = p1;
        this->p2 = p2;
        this->q1 = q1;
        this->q2 = q2;
    }
};
vector<answer> sol;

bool Compare(const answer &a, const answer &b) {
    if (a.p1 == b.p1)
        return a.q1 < b.q1;
    return a.p1 < b.p1;
}

void Insert(long double x1, long double x2, int i) {
    int p1 = d[i], p2 = a / d[i];
    int q1 = -x1 * p1, q2 = -x2 * p2;
    if (1LL * q1 * q2 == c && 1LL * p1 * p2 == a && 1LL * p1 * q2 + 1LL * p2 * q1 == b)
        sol.push_back(answer(p1, q1, p2, q2));
}

int main() {
    long long k;
    cin >> a >> b >> c >> k;
    long long delta = b * b - 4 * a * c;
    long double root = sqrt(1.0 * delta);
    if (root * root != delta) {
        cout << "-1\n";
        return 0;
    }
    delta = root;
    for (int i = 1; 1LL * i * i <= max(a, -a); i++) {
        if (a % i == 0) {
            nd++;
            d[nd] = i;
            nd++;
            d[nd] = -i;
            nd++;
            d[nd] = a / i;
            nd++;
            d[nd] = - a / i;
        }
        if (1LL * i * i == a)
            nd -= 2;
    }
    long double x1 = (long double)( - b - delta) / (long double)(2 * a);
    long double x2 = (long double)( - b + delta) / (long double)(2 * a);
    for (int i = 1; i <= nd; i++) {
        Insert(x1, x2, i);
        if (delta)
            Insert(x2, x1, i);
    }
    if (sol.size() < k) {
        cout << "-1\n";
        return 0;
    }
    sort(sol.begin(), sol.end(), Compare);
    int p1 = sol[k - 1].p1, p2 = sol[k - 1].p2, q1 = sol[k - 1].q1, q2 = sol[k - 1].q2;
    cout << "(";
    if (p1 == -1)
        cout << "-";
    else
        if (p1 != 1)
            cout << p1;
    cout << "x";
    if (q1 != 0) {
        if (q1 > 0)
            cout << "+";
        cout << q1;
    }
    cout << ")(";
    if (p2 == -1)
        cout << "-";
    else
        if (p2 != 1)
            cout << p2;
    cout << "x";
    if (q2 != 0) {
        if (q2 > 0)
            cout << "+";
        cout << q2;
    }
    cout << ")";
    return 0;
}