summaryrefslogtreecommitdiff
path: root/graph/kruskal.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'graph/kruskal.cpp')
0 files changed, 0 insertions, 0 deletions
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-24 15:57:20 +0000
id='n48' href='#n48'>48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 
#include "../util.h"
#include <math/goldenSectionSearch.cpp>

struct RandomFunction {
	ld min;
	vector<pair<ld, int>> polys;
	RandomFunction(ld l, ld r) : min(Random::real<ld>(l, r)) {
		do {
			polys.emplace_back(
				Random::real<ld>(0, 1e9),
				2 * Random::integer<int>(1, 5)
			);
		} while(false && Random::integer<int>(4) != 0);
	}

	ld operator()(ld x){
		ld res = 0;
		for (auto [m, p] : polys) {
			res += m * pow(x - min, p);
		}
		return res;
	}

	friend ostream& operator<<(ostream& os, const RandomFunction& f) {
		string plus = "";
		for (auto [m, p] : f.polys) {
			os << setprecision(15) << plus << m << "*(x-" << f.min << ")**" << p;
			plus = "+";
		}
		return os;
	}
};

void stress_test() {
	int queries = 0;
	for (int i = 0; i < 50'000; i++) {
		ld l = Random::real<double>(-200, 200);
		ld r = Random::real<double>(-200, 200);
		if (l > r) swap(l, r);

		RandomFunction f(l, r);

		ld got = gss(l, r, f);
		ld expected = f.min;
		if (float_error(got, expected) > 1e-6) {
			cerr << f << endl;
			cerr << "got: " << got << ", expected: " << expected << FAIL;
		}
		queries++;
	}
	cerr << "tested random queries: " << queries << endl;
}