Cod sursa(job #1471905)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 15 august 2015 16:35:08
Problema Rubarba Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.11 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <iomanip>
#include <cmath>

#define infile "rubarba.in"
#define outfile "rubarba.out"

//saves the abscis and the ordonate of a point
class Point {

public:

	long double x, y;

	Point() {

		x = 0;
		y = 0;

	}

	Point(long double x, long double y) {

		this->x = x;
		this->y = y;

	}

	//returns a point coresponding to an angle rotation of the plane
	Point rotatePoint(long double rotationAngle) {

		Point rotatedPoint(std::cos(rotationAngle) * x - std::sin(rotationAngle) * y, std::sin(rotationAngle) * x + std::cos(rotationAngle) * y);

		return rotatedPoint;

	}

};

//saves data of a test case
class Test {

private:

	int pointCount;

	std::vector<Point> points;

public:

	Test(int pointCount) {

		this->pointCount = pointCount;

	}

	//adds a point to the points vector
	void addPoint(Point point) {

		points.push_back(point);

	}

	//returns the number of points saved into the points vector
	int getPointCount() {

		return pointCount;

	}

	//returns a point placed at a specified index in the vector (indexed from 1)
	Point getPoint(int pointIndex) {

		return points[pointIndex - 1];

	}

};

//solves poblem "rubarba"
class Rubarba {

private:

	const long double PI = 3.141592653589;

	const long double epsilon = 1e-14;

	Test *test;

	long double solution;

	//returns the area of the minimum enclosing rectangle of the set of points from the test case rotated with a specified angle
	long double minimumEnclosingRectangle(long double rotationAngle) {

		Point rotatedPoint;

		int pointCount = test->getPointCount();

		//intitialises the minimum and maximum values of abscises and ordonates of the rotated points
		rotatedPoint = test->getPoint(1).rotatePoint(rotationAngle);

		long double maxX = rotatedPoint.x;
		long double minX = rotatedPoint.x;

		long double maxY = rotatedPoint.y;
		long double minY = rotatedPoint.y;

		//calculates the min/max values
		for (int pointIndex = 2; pointIndex <= pointCount; ++pointIndex) {

			rotatedPoint = test->getPoint(pointIndex).rotatePoint(rotationAngle);

			maxX = std::max(maxX, rotatedPoint.x);
			minX = std::min(minX, rotatedPoint.x);

			maxY = std::max(maxY, rotatedPoint.y);
			minY = std::min(minY, rotatedPoint.y);

		}

		//returns the area of the minimum enclosing rectangle
		return (maxX - minX) * (maxY - minY);

	}

public:

	//loads the test from a specified path
	void loadTest(std::string path) {

		std::ifstream file(path);

		int pointCount;

		file >> pointCount;

		test = new Test(pointCount);

		for (int pointIndex = 1; pointIndex <= pointCount; ++pointIndex) {

			long double x, y;

			file >> x >> y;

			test->addPoint(Point(x, y));

		}

		file.close();

	}

	//solves the problem
	void solve() {

		//we find the rotation angle for the minimum enclosing rectangle of the set of points from the test case
		//for that we will use ternary search because the f(rotation angle) = (min enclosing rectangle) function is bitonic and accepts a minimum
		long double left = 0, right = PI / 2.0;

		while (right - left >= epsilon) {

			long double smallThird = left + (right - left) / 3.0;
			long double bigThird = right - (right - left) / 3.0;

			if (minimumEnclosingRectangle(smallThird) < minimumEnclosingRectangle(bigThird)) {

				right = bigThird;

			}
			else {

				left = smallThird;

			}

		}

		//saves the value of the angle thet gives the smallest rectangle
		solution = left;

	}

	//writes the solution to a specified path
	void writeSolution(std::string path) {

		std::ofstream file(path);

		file << std::setprecision(2) << std::fixed << minimumEnclosingRectangle(solution);

		file.close();

	}

};

int main() {

	//creates an instance of the Rubarba class
	Rubarba rubarba;

	//loads the test case
	rubarba.loadTest(infile);

	//solves the problem
	rubarba.solve();

	//writes the solution
	rubarba.writeSolution(outfile);

	return 0;

}

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