Pagini recente » Cod sursa (job #1253389) | Cod sursa (job #1685485) | Cod sursa (job #263472) | Cod sursa (job #2499124) | Cod sursa (job #1723588)
#include <fstream>
#include <iomanip>
#include <cmath>
using namespace std;
const int N_MAX = 100010;
const double Eps = 1e-15;
const double Inf = 1e20;
const double Pi = acos(-1.0);
int N;
double X[N_MAX];
double Y[N_MAX];
int Sign(double x) {
return (x < -Eps ? -1 : (x > Eps ? 1 : 0));
}
void Max(double &x, double y) {
if(Sign(x - y) == -1)
x = y;
}
void Min(double &x, double y) {
if(Sign(x - y) == 1)
x = y;
}
/** This function has a minimum which will be determined by the ternary search */
double getBoxArea(double Rotation) {
double xMin = Inf, xMax = -Inf, yMin = Inf, yMax = -Inf, Sin = sin(Rotation), Cos = cos(Rotation);
for(int i = 1; i <= N; i++) {
double xNew = X[i] * Cos - Y[i] * Sin;
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 */
double ternarySearch() {
double Lo = 0, Hi = Pi / 2;
while(Sign(Lo - Hi) != 0) {
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;
}