Cod sursa(job #167782)

Utilizator tm_raduToma Radu tm_radu Data 30 martie 2008 01:47:05
Problema Ecuatie Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.21 kb
#include <stdio.h>
#include <vector>
#include <math.h>
using namespace std;

int a, b, c, k;
int i, j, h, g, d, delta;
double x1, x2;
int p1, p2, q1, q2;
struct e {
	int p1, p2, q1, q2;
};
vector<e> sol;
    
void Verif(int div);
void Qsort(int st, int dr);
void Print();

int main()
{
    freopen("ecuatie.in", "r", stdin);
    freopen("ecuatie.out", "w", stdout);
    scanf("%d %d %d %d", &a, &b, &c, &k);
    j = (int)sqrt((double)a);
    delta = b*b - 4*a*c;
    h = (int)sqrt((double)delta);
    // no solution
    if ( delta != h*h ) 
    {
        printf("-1\n");
        return 0;
    }
    x1 = (double)(-b - h)/(double)(2*a);
    x2 = (double)(-b + h)/(double)(2*a);
    e str; str.p1 = str.p2 = str.q1 = str.q2 = 0;
    sol.push_back(str);
    // chacking
    for ( i = 1; i <= j; i++ )
        if ( a % i == 0 )
        {
            Verif(i);
            Verif(-i);
            Verif(a/i);
            Verif(-a/i);
        }
    Qsort(1, sol.size()-1);    
    Print();

    return 0;
}

void Verif(int div)
{
    int ok;
    // first case
    p1 = div;
    q1 = (int)(-x1*div);
    p2 = a/div;
    q2 = (int)(-x2*(a/div));
    if ( p1*p2 == a && (p2*q1 + p1*q2) == b && q1*q2 == c ) 
    {
        e pct;
        pct.p1 = p1; pct.p2 = p2; pct.q1 = q1; pct.q2 = q2;
        ok = 1;
        for ( int g = 1; g < sol.size(); g++ )
            if ( sol[g].p1 == pct.p1 && sol[g].p2 == pct.p2 && sol[g].q1 == pct.q1 && sol[g].q2 == pct.q2 ) ok = 0;
        if ( ok ) sol.push_back(pct);
    }
    // second case
    p1 = div;
    q1 = (int)(-x2*div);
    p2 = a/div;
    q2 = (int)(-x1*(a/div));
	if ( p1*p2 == a && (p2*q1 + p1*q2) == b && q1*q2 == c )
    {
        e pct;
        pct.p1 = p1; pct.p2 = p2; pct.q1 = q1; pct.q2 = q2;
        ok = 1;
        for ( int g = 1; g < sol.size(); g++ )
            if ( sol[g].p1 == pct.p1 && sol[g].p2 == pct.p2 && sol[g].q1 == pct.q1 && sol[g].q2 == pct.q2 ) ok = 0;
        if ( ok ) sol.push_back(pct);
    }
}

void Qsort(int st, int dr)
{
    int i = st-1;
    int j = dr+1;
    do
    {
        do { i++; } while ( sol[i].p1 < sol[st].p1 || (sol[i].p1 == sol[st].p1 && sol[i].q1 < sol[st].q1) );
        do { j--; } while ( sol[st].p1 < sol[j].p1 || (sol[st].p1 == sol[j].p1 && sol[st].q1 < sol[j].q1) );
        if ( i <= j )
        {
            e aux = sol[i];
            sol[i] = sol[j];
            sol[j] = aux;
        }
    } while ( i <= j );
    if ( i < dr ) Qsort(i, dr);
    if ( st < j ) Qsort(st, j);
}

void Print()
{
    p1 = sol[k].p1;
    p2 = sol[k].p2;
    q1 = sol[k].q1;
    q2 = sol[k].q2;
    printf("(");
    if ( p1 == 1 ) printf("x");
    if ( p1 == -1 ) printf("-x");
    if ( p1 != 1 && p1 != -1 && p1 > 0 ) printf("%dx", p1);
    if ( p1 != 1 && p1 != -1 && p1 < 0 ) printf("-%dx", p1);
    if ( q1 >= 0 ) printf("+%d)(", q1);
    else           printf("%d)(", q1); 
    if ( p2 == 1 ) printf("x");
    if ( p2 == -1 ) printf("-x");
    if ( p2 != 1 && p2 != -1 && p2 > 0 ) printf("%dx", p2);
    if ( p2 != 1 && p2 != -1 && p2 < 0 ) printf("-%dx", p2);
    if ( q2 >= 0 ) printf("+%d)\n", q2);
    else           printf("%d)\n", q2); 
}