Cod sursa(job #132448)

Utilizator Darth_NiculusIvan Nicolae Darth_Niculus Data 5 februarie 2008 20:48:38
Problema Ecuatie Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.7 kb
/* Ivan Nicolae - Bucuresti */
/* Ecuatie  - Infoarena */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define NMAX 31625
#define INPUT  "ecuatie.in"
#define OUTPUT "ecuatie.out"

struct Sol
{ int p1,q1,p2,q2; } sol[NMAX],rez,B[NMAX];

int a,b,c,P1,P2,Q1,Q2,k,s;
double x1,x2;

void Merge_q1(int li, int ls)
{
 int m = (li+ls)/2, i ,j, k;
 if (li==ls) return;
 Merge_q1(li,m);
 Merge_q1(m+1,ls);
 for (i=li, j=m+1, k=li; i<=m || j<=ls;)
    if (j>ls || (i<=m && sol[i].q1 < sol[j].q1))
      B[k++]=sol[i++];
      else B[k++]=sol[j++];
 for (k=li;k<=ls;k++) sol[k]=B[k];
}

void Merge_p1(int li, int ls)
{
 int m = (li+ls)/2, i ,j, k;
 if (li==ls) return;
 Merge_p1(li,m);
 Merge_p1(m+1,ls);
 for (i=li, j=m+1, k=li; i<=m || j<=ls;)
    if (j>ls || (i<=m && sol[i].p1 <= sol[j].p1))
      B[k++]=sol[i++];
      else B[k++]=sol[j++];
 for (k=li;k<=ls;k++) sol[k]=B[k];
}

int main()
{
 freopen(INPUT,"r",stdin);
 freopen(OUTPUT,"w",stdout);

 scanf("%d%d%d%d",&a,&b,&c,&k);
 
 int delta=b*b-4*a*c;
 if (((double)sqrt(delta)) != (double)((int)sqrt(delta)))
   printf("-1\n");
   else {
         x1=(double)((-1)*b+sqrt(delta))/(2*a);
         x2=(double)((-1)*b-sqrt(delta))/(2*a);

         s=0;
         for (int d=1;d<=sqrt(a);d++)
            if (!(a % d))
              {
               // P1 = d
               P1=d;
               P2=a/P1;
               Q1=(-1)*x1*P1;
               Q2=(-1)*x2*P2;
               sol[++s].p1=P1; sol[s].p2=P2; sol[s].q1=Q1; sol[s].q2=Q2;
               Q1=(-1)*x2*P1;
               Q2=(-1)*x1*P2;
               sol[++s].p1=P1; sol[s].p2=P2; sol[s].q1=Q1; sol[s].q2=Q2;
               // P1 = -d
               P1=(-1)*d;
               P2=a/P1;
               Q1=(-1)*x1*P1;
               Q2=(-1)*x2*P2;
               sol[++s].p1=P1; sol[s].p2=P2; sol[s].q1=Q1; sol[s].q2=Q2;
               Q1=(-1)*x2*P1;
               Q2=(-1)*x1*P2;
               sol[++s].p1=P1; sol[s].p2=P2; sol[s].q1=Q1; sol[s].q2=Q2;
               // P1 = a/d
               P1=a/d;
               P2=a/P1;
               Q1=(-1)*x1*P1;
               Q2=(-1)*x2*P2;
               sol[++s].p1=P1; sol[s].p2=P2; sol[s].q1=Q1; sol[s].q2=Q2;
               Q1=(-1)*x2*P1;
               Q2=(-1)*x1*P2;
               sol[++s].p1=P1; sol[s].p2=P2; sol[s].q1=Q1; sol[s].q2=Q2;               
               // P1 = -a/d
               P1=(-1)*a/d;
               P2=a/P1;
               Q1=(-1)*x1*P1;
               Q2=(-1)*x2*P2;
               sol[++s].p1=P1; sol[s].p2=P2; sol[s].q1=Q1; sol[s].q2=Q2;
               Q1=(-1)*x2*P1;
               Q2=(-1)*x1*P2;
               sol[++s].p1=P1; sol[s].p2=P2; sol[s].q1=Q1; sol[s].q2=Q2;               
              }
         if (s && k<=s)
           {
            Merge_q1(1,s);
            Merge_p1(1,s);
            int kk=0;
            for (int j=1;j<=s;j++)
               if (sol[j].p1 != sol[j-1].p1 || sol[j].p2 != sol[j-1].p2 || sol[j].q1 != sol[j-1].q1 || sol[j].q2 != sol[j-1].q2)
                 { kk++; if (kk==k) rez=sol[j]; }
            int p1=rez.p1,p2=rez.p2,q1=rez.q1,q2=rez.q2;
            printf("(");
            if (p1 != 1 && p1 != -1) printf("%d",p1);
            if (p1 == -1) printf("-");
            printf("x");
            if (q1 >=0) printf("+%d",q1);
              else printf("%d",q1);
            printf(")(");
            if (p2 != 1 && p2 != -1) printf("%d",p2);
            if (p2 == -1) printf("-");
            printf("x");
            if (q2 >=0) printf("+%d",q2);
              else printf("%d",q2);
            printf(")\n");
           }
           else printf("-1\n");
        }

 fclose(stdin);
 fclose(stdout);
 return 0;
}