Egalitarianism2.cpp

#include <bits/stdc++.h>
using namespace std;

class Egalitarianism2
{
public:
	double minStdev(vector <int> x, vector <int> y);
};

double Egalitarianism2::minStdev (vector <int> x, vector <int> y)
{
	double ret;
	return ret;
}

// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit-pf 2.3.0
#include <iostream>
#include <string>
#include <vector>
#include <ctime>
#include <cmath>
using namespace std;
bool KawigiEdit_RunTest(int testNum, vector <int> p0, vector <int> p1, bool hasAnswer, double p2) {
	cout << "Test " << testNum << ": [" << "{";
	for (int i = 0; int(p0.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << p0[i];
	}
	cout << "}" << "," << "{";
	for (int i = 0; int(p1.size()) > i; ++i) {
		if (i > 0) {
			cout << ",";
		}
		cout << p1[i];
	}
	cout << "}";
	cout << "]" << endl;
	Egalitarianism2 *obj;
	double answer;
	obj = new Egalitarianism2();
	clock_t startTime = clock();
	answer = obj->minStdev(p0, p1);
	clock_t endTime = clock();
	delete obj;
	bool res;
	res = true;
	cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;
	if (hasAnswer) {
		cout << "Desired answer:" << endl;
		cout << "\t" << p2 << endl;
	}
	cout << "Your answer:" << endl;
	cout << "\t" << answer << endl;
	if (hasAnswer) {
		res = answer == answer && fabs(p2 - answer) <= 1e-9 * max(1.0, fabs(p2));
	}
	if (!res) {
		cout << "DOESN'T MATCH!!!!" << endl;
	} else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2) {
		cout << "FAIL the timeout" << endl;
		res = false;
	} else if (hasAnswer) {
		cout << "Match :-)" << endl;
	} else {
		cout << "OK, but is it right?" << endl;
	}
	cout << "" << endl;
	return res;
}
int main() {
	bool all_right;
	bool disabled;
	bool tests_disabled;
	all_right = true;
	tests_disabled = false;
	
	vector <int> p0;
	vector <int> p1;
	double p2;
	
	// ----- test 0 -----
	disabled = false;
	p0 = {0,0,1,1};
	p1 = {0,1,0,1};
	p2 = 0.0;
	all_right = (disabled || KawigiEdit_RunTest(0, p0, p1, true, p2) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	
	// ----- test 1 -----
	disabled = false;
	p0 = {0,0,0};
	p1 = {0,9,10};
	p2 = 0.5;
	all_right = (disabled || KawigiEdit_RunTest(1, p0, p1, true, p2) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	
	// ----- test 2 -----
	disabled = false;
	p0 = {12,46,81,56};
	p1 = {0,45,2,67};
	p2 = 6.102799971320872;
	all_right = (disabled || KawigiEdit_RunTest(2, p0, p1, true, p2) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	
	// ----- test 3 -----
	disabled = false;
	p0 = {0,0,0,0,0,0,0};
	p1 = {0,2,3,9,10,15,16};
	p2 = 0.9428090415820617;
	all_right = (disabled || KawigiEdit_RunTest(3, p0, p1, true, p2) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	
	// ----- test 4 -----
	disabled = false;
	p0 = {167053,536770,-590401,507047,350178,-274523,-584679,-766795,-664177,267757,-291856,-765547,604801,-682922,-404590,468001,607925,503849,-499699,-798637};
	p1 = {-12396,-66098,-56843,20270,81510,-23294,10423,24007,-24343,-21587,-6318,-7396,-68622,56304,-85680,-14890,-38373,-25477,-38240,11736};
	p2 = 40056.95946451678;
	all_right = (disabled || KawigiEdit_RunTest(4, p0, p1, true, p2) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	
	// ----- test 5 -----
	disabled = false;
	p0 = {-306880,169480,-558404,-193925,654444,-300247,-456420,-119436,-620920,-470018,-914272,-691256,-49418,-21054,603373,-23656,891691,258986,-453793,-782940};
	p1 = {-77318,-632629,-344942,-361706,191982,349424,676536,166124,291342,-268968,188262,-537953,-70432,156803,166174,345128,58614,-671747,508265,92324};
	p2 = 36879.1512763429;
	all_right = (disabled || KawigiEdit_RunTest(5, p0, p1, true, p2) ) && all_right;
	tests_disabled = tests_disabled || disabled;
	// ------------------
	
	if (all_right) {
		if (tests_disabled) {
			cout << "You're a stud (but some test cases were disabled)!" << endl;
		} else {
			cout << "You're a stud (at least on given cases)!" << endl;
		}
	} else {
		cout << "Some of the test cases had errors." << endl;
	}
	return 0;
}
// PROBLEM STATEMENT
// There are N cities in the plane.
// For convenience, the cities are numbered 0 through N-1.
// For each i, the city number i is represented by the point at coordinates (x[i], y[i]).
// 
// 
// The king wants to connect all cities by building exactly N-1 roads.
// Each road must connect two cities.
// All roads must be straight.
// Hence, the length of a road is equal to the Euclidean distance between the two points it connects.
// The roads are allowed to cross and even overlap arbitrarily.
// (You cannot change roads at a crossing.
// Hence, the N-1 roads connect all cities if and only if their topology is a tree.)
// 
// 
// The king does not care about roads being short.
// However, people often complain if some roads are short and others are long.
// Therefore, the king would like to select a set of N-1 roads such that they connect all cities, and the standard deviation of the sequence of their lengths is as small as possible.
// 
// 
// Formally, given a sequence of real numbers (a1,...,aS) we can compute their standard deviation as follows.
// First, let b = ((a1+...+aS) / S) be their mean - i.e., the average of our numbers.
// Next, let c = (sum_i (b-ai)^2) be the sum of squared distances of all values from the mean.
// Finally, the standard deviation of our sequence is computed as sqrt(c/S).
// Note that our sequence will contain exactly N-1 road lengths, hence in the above formulas S will be equal to N-1.
// 
// 
// You are given the vector <int>s x and y with N elements each: the coordinates of the N points.
// Compute and return the smallest possible value of the standard deviation of lengths of selected roads.
// 
// DEFINITION
// Class:Egalitarianism2
// Method:minStdev
// Parameters:vector <int>, vector <int>
// Returns:double
// Method signature:double minStdev(vector <int> x, vector <int> y)
// 
// 
// NOTES
// -The Euclidean distance between points (a,b) and (c,d) equals sqrt( (a-c)^2 + (b-d)^2 ).
// -Your return value must have an absolute or a relative error of less than 1e-9.
// 
// 
// CONSTRAINTS
// -x will contain between 3 and 20 elements, inclusive.
// -x and y will contain same number of elements.
// -Each element in x will be between -1,000,000 and 1,000,000, inclusive.
// -Each element in y will be between -1,000,000 and 1,000,000, inclusive.
// -No two cities will be located in the same place.
// 
// 
// EXAMPLES
// 
// 0)
// {0,0,1,1}
// {0,1,0,1}
// 
// Returns: 0.0
// 
// We can build these roads: 0-1, 1-3, 3-2.
// 
// 1)
// {0,0,0}
// {0,9,10}
// 
// Returns: 0.5
// 
// The optimal solution is to build the roads with lengths 9 and 10. (Note that these two roads overlap, but that is allowed.)
// 
// 2)
// {12,46,81,56}
// {0,45,2,67}
// 
// Returns: 6.102799971320872
// 
// 
// 
// 3)
// {0,0,0,0,0,0,0}
// {0,2,3,9,10,15,16}
// 
// Returns: 0.9428090415820617
// 
// 
// 
// 4)
// {167053, 536770, -590401, 507047, 350178, -274523, -584679, -766795, -664177, 267757, -291856, -765547, 604801, -682922, -404590, 468001, 607925, 503849, -499699, -798637}
// {-12396, -66098, -56843, 20270, 81510, -23294, 10423, 24007, -24343, -21587, -6318, -7396, -68622, 56304, -85680, -14890, -38373, -25477, -38240, 11736}
// 
// Returns: 40056.95946451678
// 
// 
// 
// 5)
// {-306880, 169480, -558404, -193925, 654444, -300247, -456420, -119436, -620920, -470018, -914272, -691256, -49418, -21054, 603373, -23656, 891691, 258986, -453793, -782940}
// {-77318, -632629, -344942, -361706, 191982, 349424, 676536, 166124, 291342, -268968, 188262, -537953, -70432, 156803, 166174, 345128, 58614, -671747, 508265, 92324}
// 
// Returns: 36879.1512763429
// 
// 
// 
// END KAWIGIEDIT TESTING