Pagini recente » Cod sursa (job #1914940) | Cod sursa (job #19466) | Cod sursa (job #1219979) | Cod sursa (job #185575) | Cod sursa (job #1723589)
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;
const int N_MAX = 100010;
const long double Eps = 1e-18;
const long double Inf = 1e20;
const long double Pi = acos(-1.0);
int N;
long double X[N_MAX];
long double Y[N_MAX];
int Sign(long double x) {
return (x < -Eps ? -1 : (x > Eps ? 1 : 0));
}
void Max(long double &x, long double y) {
if(Sign(x - y) == -1)
x = y;
}
void Min(long double &x, long double y) {
if(Sign(x - y) == 1)
x = y;
}
/** 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;
Max(xMax, xNew);
Min(xMin, xNew);
Max(yMax, yNew);
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(Sign(Lo - Hi) != 0) {
long double Mid = (Lo + Hi) * 0.5;
if(Sign(getBoxArea(Mid) - getBoxArea(Mid + Eps)) == 1) 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;
}