Cod sursa(job #485818)

Utilizator taloibogdanTaloi Bogdan Cristian taloibogdan Data 19 septembrie 2010 16:50:33
Problema Ecuatie Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
long a,b,c,d,k,aa,x1,x2,i,delta,l,f;
struct che{long p1,q1,p2,q2;}pq[1000000];
long cmp(che a,che b)
{if(a.p1<b.p1)return 1;
 if(a.p1>b.p1)return 0;
 if(a.q1>b.q1)return 0;
 return 1;}
int main()
{
 freopen("ecuatie.in","r",stdin);
 freopen("ecuatie.out","w",stdout);
 scanf("%ld%ld%ld%ld",&a,&b,&c,&k);
 delta=b*b-4*a*c;
 if(delta<0){printf("-1\n");return 0;}
 if(labs(sqrt(delta)-(long)sqrt(delta))>=0.000001){printf("-1\n");return 0;}
 d=sqrt(delta);
 aa=sqrt(labs(a));
 x1=(-b-d)/(2*a);
 x2=(-b+d)/(2*a);
 for(i=1;i<=aa;++i)
    if(a%i==0)
    {pq[++l].p1=i;
     pq[l].q1=-x1*i;
     pq[l].p2=a/i;
     pq[l].q2=-x2*(a/i);
     pq[++l].p1=i;
     pq[l].q1=-x2*i;
     pq[l].p2=a/i;
     pq[l].q2=-x1*(a/i);

     pq[++l].p2=i;
     pq[l].q2=-x1*i;
     pq[l].p1=a/i;
     pq[l].q1=-x2*(a/i);
     pq[++l].p2=i;
     pq[l].q2=-x2*i;
     pq[l].p1=a/i;
     pq[l].q1=-x1*(a/i);

     pq[++l].p1=(-i);
     pq[l].q1=-x1*(-i);
     pq[l].p2=a/(-i);
     pq[l].q2=-x2*(a/(-i));
     pq[++l].p1=(-i);
     pq[l].q1=-x2*(-i);
     pq[l].p2=a/(-i);
     pq[l].q2=-x1*(a/(-i));

     pq[++l].p2=(-i);
     pq[l].q2=-x1*(-i);
     pq[l].p1=a/(-i);
     pq[l].q1=-x2*(a/(-i));
     pq[++l].p2=(-i);
     pq[l].q2=-x2*(-i);
     pq[l].p1=a/(-i);
     pq[l].q1=-x1*(a/(-i));
    }
 sort(pq+1,pq+l+1,cmp);
 f=0;
 for(i=1;i<=l&&f<k;++i)if(pq[i].p1!=pq[i-1].p1||pq[i].p2!=pq[i-1].p2||pq[i].q1!=pq[i-1].q1||pq[i].q2!=pq[i-1].q2)++f;
 i--;
 if(f<k){printf("-1\n");return 0;}
 a=pq[i].p1;
 b=pq[i].q1;
 c=pq[i].p2;
 d=pq[i].q2;
 printf("(");
 if(a>1||a<-1)printf("%ld",a);
 if(a==-1)printf("-");
 printf("x");
 if(b>0)printf("+");
 printf("%ld)(",b);
 if(c>1||c<-1)printf("%ld",c);
 if(c==-1)printf("-");
 printf("x");
 if(d>0)printf("+");
 printf("%ld)\n",d);
 return 0;
}