Cod sursa(job #995060)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 7 septembrie 2013 10:30:27
Problema Ecuatie Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.7 kb
#include<fstream>
#include<math.h>
#include <algorithm>

using namespace std;

ifstream fin ("ecuatie.in");
ofstream fout ("ecuatie.out");


void quickSort(long long numbers[], int array_size);
void q_sort(long long numbers[], int left, int right);
void citire();
long long verific_delta();
void construire_div();
void construire_sol(long double  x,long double y,int poz);
int verific(int t);
void sortez();
void afisare(long long k);

long long a,b,c,k,i,j,m,p[20000];
struct ecuatie{long p1,q1,p2,q2;}v[10000],aux;

int main()
{
    citire();
    long long h=verific_delta();
    if(h!=0)
        {   long double x1=(long double )(-b-h)/(long double )(2*a);
            long double x2=(long double )(-b+h)/(long double )(2*a);
            construire_div();
            for(i=0,j=0;i<m;i++)
                { construire_sol(x1,x2,j);
                  if(verific(j)!=0)
                    j++;
                  construire_sol(x2,x1,j);
                  if(verific(j)!=0)
                    j++;
                }
            sortez();
            k--;
            j--;
            if(k>j||j==0)           fout<<"-1";
            else          afisare(k);
        }
    else
        fout<<"-1";

    return 0;
}

void citire()
{   fin>>a>>b>>c>>k;      }

long long verific_delta()
{
    long long delta=b*b-4*a*c;
    if(delta<0)
        return 0;
    else
        {
        long double m=sqrt(delta);
        if(delta==m*m)
            return m;
        }
return 0;
}

void construire_div()
{
    int l=0,i;
    long long d[20000];
    for(i=1;i<=sqrt(abs(a));i++)
        if(a%i==0)
        {
            d[l++]=i;
            d[l++]=-i;
            d[l++]=a/i;
            d[l++]=-a/i;
        }

    q_sort(d,0,l-1);
    m=0;
    for(i=0;i<l;i++)
        if(d[i]!=d[i+1])
            p[m++]=d[i];
}

void construire_sol(long double x,long double y,int poz)
{
    v[poz].p1=p[i];
    v[poz].q1=-x*p[i];
    v[poz].p2=a/p[i];
    v[poz].q2=-y*(a/p[i]);
}

int verific(int t)
{
    if((v[t].p1!=0&&v[t].q1!=0&&v[t].p2!=0&&v[t].q2!=0)&&(v[t].q1*v[t].q2==c)&&((v[t].p1*v[t].p2)==a)&&(v[t].p1*v[t].q2+v[t].q1*v[t].p2)==b)
        return 1;

    return 0;
}

void sortez()
{

    for(i=0;i<=j;i++)
         if(v[i].p1==v[i+1].p1)
        if(v[i].q1>v[i+1].q1)
                {
                aux=v[i];
                v[i]=v[i+1];
                v[i+1]=aux;
                }

}

void afisare(long long k)
{

      if(v[k].p1==1)            fout<<"(x";
      else
        if(v[k].p1==-1)     fout<<"(-x";
        else            fout<<"("<<v[k].p1<<"x";
            if(v[k].q1>0)   fout<<"+"<<v[k].q1<<")";
            else        fout<<v[k].q1<<")";

      if(v[k].p2==1)            fout<<"(x";
      else
        if(v[k].p2==-1)     fout<<"(-x";
        else            fout<<"("<<v[k].p2<<"x";
            if(v[k].q2>0)   fout<<"+"<<v[k].q2<<")";
            else        fout<<v[k].q2<<")";

}

void q_sort(long long numbers[], int left, int right)
{
   long long pivot, l_hold, r_hold;
   l_hold = left;
   r_hold = right;
   pivot = numbers[left];
   while (left < right)
   {
      while ((numbers[right] >= pivot) && (left < right))
      right--;
      if (left != right)
      {
     numbers[left] = numbers[right];
     left++;
      }
      while ((numbers[left] <= pivot) && (left < right))
     left++;
      if (left != right)
      {
      numbers[right] = numbers[left];
      right--;
      }
   }
   numbers[left] = pivot;
   pivot = left;
   left = l_hold;
   right = r_hold;
   if (left < pivot)
      q_sort(numbers, left, pivot-1);
   if (right > pivot)
      q_sort(numbers, pivot+1, right);
}