Pagini recente » Cod sursa (job #1530130) | Cod sursa (job #1512114) | Cod sursa (job #2960294) | Cod sursa (job #138059) | Cod sursa (job #1723592)
/** Baga-mi-as pula in precizia voastra! (C) 2016 Vlad Dumitru */
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;
const int N_MAX = 100010;
const long double Eps = 1e-17;
const long double Inf = 1e20;
const long double Pi = acos(-1.0);
int N;
long double X[N_MAX];
long double Y[N_MAX];
/** This function has a minimum which will be determined by the ternary search */
long double getBoxArea(long double Rotation) {
long double xMin = Inf, xMax = -Inf, yMin = Inf, yMax = -Inf, Sin = sin(Rotation), Cos = cos(Rotation);
for(int i = 1; i <= N; i++) {
long double xNew = X[i] * Cos - Y[i] * Sin;
long double yNew = X[i] * Sin + Y[i] * Cos;
xMax = max(xMax, xNew);
yMax = max(yMax, yNew);
xMin = min(xMin, xNew);
yMin = min(yMin, yNew);
}
return (xMax - xMin) * (yMax - yMin);
}
/** Employing the great trick of comparing Mid to Mid + Eps -- Equivalent to comparing the thirds */
long double ternarySearch() {
long double Lo = 0, Hi = Pi / 2;
while(Lo + Eps < Hi) {
long double Mid = (Lo + Hi) * 0.5;
if(getBoxArea(Mid) > getBoxArea(Mid + Eps)) Lo = Mid;
else Hi = Mid;
}
return Lo;
}
int main() {
ifstream f("rubarba.in");
ofstream g("rubarba.out");
f >> N;
for(int i = 1; i <= N; i++)
f >> X[i] >> Y[i];
g << setprecision(2) << fixed << getBoxArea(ternarySearch());
return 0;
}