Cod sursa(job #1463485)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 21 iulie 2015 00:52:01
Problema Ecuatie Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>

#define infile "ecuatie.in"
#define outfile "ecuatie.out"
#define DIM 20005

using namespace std;

ifstream fin(infile);
ofstream fout(outfile);

long long A, B, C, k;

int divs[DIM], nrDivs, i;

struct solution{

	int p1, p2;

	int q1, q2;

	solution() {}

	solution(int p1, int q1, int p2, int q2) {

		this->p1 = p1;
		this->q1 = q1;
		this->p2 = p2;
		this->q2 = q2;

	}

};

bool cmp(const solution &a, const solution &b) {

	return(a.p1 == b.p1 ? a.q1 < b.q1 : a.p1 < b.p1);

}

vector<solution> SOL;

void insertSOL(long double  x1, long double x2) {

	int P1 = divs[i];
	int P2 = A/divs[i];
	int Q1 = -x1*P1;
	int Q2 = -x2*P2;

	if (1LL * Q1 * Q2 == C && 1LL * P1*P2 == A && 1LL * P1*Q2 + 1LL * P2*Q1 == B)
		SOL.push_back(solution(P1, Q1, P2, Q2));

}

int main() {

	fin >> A >> B >> C >> k;

	long long D = B*B - 4 * A*C;

	long double t = sqrt(D*1.0);

	if (D != t*t) {

		fout << -1;

		return 0;

	}

	D = t;

	for (int i = 1; 1LL*i*i <= max(A, -A); ++i) {

		if (A % i == 0) {

			divs[++nrDivs] = i;
			divs[++nrDivs] = -i;
			divs[++nrDivs] = A/i;
			divs[++nrDivs] = -A/i;

		}

		if (1LL * i * i == A)
			nrDivs -= 2;

	}

	long double x1 = (long double)(-B - D) / (long double)(2 * A);
	long double x2 = (long double)(-B + D) / (long double)(2 * A);

	for (i = 1; i <= nrDivs; ++i) {

		insertSOL(x1, x2);

		if (D) {

			insertSOL(x2, x1);

		}


	}

	if (SOL.size() < k) {

		fout << "-1";

		return 0;

	}

	sort(SOL.begin(), SOL.end(), cmp);

	int p1 = SOL[k - 1].p1;
	int p2 = SOL[k - 1].p2;
	int q1 = SOL[k - 1].q1;
	int q2 = SOL[k - 1].q2;

	fout << '(';

	if (p1 == -1)
		fout << '-';
	else
		if (p1 != 1)
			fout << p1;

	fout << 'x';

	if (q1 != 0) {

		if (q1 > 0)
			fout << '+';

		fout << q1;

	}

	fout << ")(";

	if (p2 == -1)
		fout << '-';
	else
		if (p2 != 1)
			fout << p2;

	fout << 'x';

	if (q2 != 0) {

		if (q2 > 0)
			fout << '+';

		fout << q2;

	}

	fout << ')';

	return 0;

}

//Trust me, I'm the Doctor!
//Miriam e tare!