Pagini recente » clasament-arhiva-educationala | Borderou de evaluare (job #2236706) | Clasamentul arhivei educationale | Cod sursa (job #1481403) | Cod sursa (job #1471905)
#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!