Cod sursa(job #312570)

Utilizator tvladTataranu Vlad tvlad Data 6 mai 2009 14:20:26
Problema Ecuatie Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

struct solutie {
	int p1, q1, p2, q2;
	solutie() {}
	solutie ( int P1, int Q1, int P2, int Q2 ) { p1 = P1; p2 = P2; q1 = Q1; q2 = Q2; }
};
bool operator< ( const solutie &a, const solutie &b ) { return a.p1 == b.p1 ? a.q1 < b.q1 : a.p1 < b.p1; }
bool operator== ( const solutie &a, const solutie &b ) { return a.p1 == b.p1 && a.q1 == b.q1 && a.p2 == b.p2 && a.q2 == b.q2; }

const double EPS = 1e-7;

int a,b,c,k;
double x1,x2;
vector<solutie> vsol;

template <class T> inline bool integer ( T a ) {
	return fabs(a - (int)a) < EPS;
}

void process ( int p1 ) {
	double q1,p2,q2;
	q1 = -x1 * p1;
	p2 = a / p1;
	q2 = -x2 * p2;
	if (integer(q1) && integer(q2)) {
		vsol.push_back(solutie(p1,q1,p2,q2));
		vsol.push_back(solutie(p2,q2,p1,q1));
	}
}

void writepair ( int p, int q ) {
	int qn; char semn;
	if (q < 0) {
		qn = -q;
		semn = '-';
	} else {
		qn = q;
		semn = '+';
	}
	if (p == 0) printf("%d",q); else
	if (p == 1) printf("(x%c%d)",semn,qn); else
	if (p == -1) printf("(-x%c%d)",semn,qn); else
		printf("(%dx%c%d)",p,semn,qn);
}

int main() {
	freopen("ecuatie.in","rt",stdin);
	freopen("ecuatie.out","wt",stdout);
	scanf("%d %d %d %d",&a,&b,&c,&k);
	
	long long delta = b*b - 4*a*c;
	int sqd = (int)sqrt((long double)delta);
	if ((long long)sqd*sqd != delta) {
		printf("-1\n");
		return 0;
	}
	x1 = (double)(-b + sqd) / (2*a);
	x2 = (double)(-b - sqd) / (2*a);

	for (int i = 1; i*i <= a; ++i) {
		if (a % i == 0) {
			process(i);
			process(a/i);
			process(-i);
			process(-a/i);
		}
	}
	sort(vsol.begin(),vsol.end());
	vsol.resize( unique(vsol.begin(), vsol.end()) - vsol.begin() );
	if (vsol.size() < k) {
		printf("-1\n");
		return 0;
	}
	writepair(vsol[k-1].p1,vsol[k-1].q1);
	writepair(vsol[k-1].p2,vsol[k-1].q2);
	return 0;
}