Cod sursa(job #304601)

Utilizator gabor_oliviu1991gaboru corupt gabor_oliviu1991 Data 14 aprilie 2009 15:40:10
Problema Ecuatie Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.14 kb
#include<fstream>
#include<cmath>
#include <cstdio>

using namespace std;

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);

ifstream f("ecuatie.in");
ofstream g("ecuatie.out");

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)
			     afisare(k);
            else
                 g<<"-1";
		}
	else
		g<<"-1";

	return 0;
}

void citire()
{	f>>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;
	long long d[2000];
	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)			g<<"(x";
      else
		if(v[k].p1==-1)  	g<<"(-x";
		else  			g<<"("<<v[k].p1<<"x";
			if(v[k].q1>0)   g<<"+"<<v[k].q1<<")";
			else   		g<<v[k].q1<<")";

      if(v[k].p2==1)   			g<<"(x";
      else
		if(v[k].p2==-1)  	g<<"(-x";
		else       		g<<"("<<v[k].p2<<"x";
			if(v[k].q2>0)   g<<"+"<<v[k].q2<<")";
			else  		g<<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);
}