Pagini recente » Istoria paginii utilizator/cineva15 | Cod sursa (job #740751) | Istoria paginii runda/ki | Cod sursa (job #2112133) | Cod sursa (job #1724009)
#include <fstream>
#include <cmath>
#include <algorithm>
#include <limits>
using namespace std;
constexpr int MAX_N = 100000;
constexpr double EPS = 1e-15;
pair <int, int> V[MAX_N];
pair <double, double> rotatePoint(const pair <int, int> &A,
const pair <double, double> &rotationMatrix) {
return make_pair(A.first * rotationMatrix.first - A.second * rotationMatrix.second,
A.first * rotationMatrix.second + A.second * rotationMatrix.first);
}
double retangleArea(const double radians, const int n) {
pair <double, double> rotationMatrix = make_pair(cos(radians), sin(radians));
double min_x = 1e30, max_x = -1e30, min_y = 1e30, max_y = -1e30;
for (int i = 0; i < n; i += 1) {
pair <double, double> T = rotatePoint(V[i], rotationMatrix);
if (T.first < min_x) {
min_x = T.first;
}
if (T.first > max_x) {
max_x = T.first;
}
if (T.second < min_y) {
min_y = T.second;
}
if (T.second > max_y) {
max_y = T.second;
}
}
return (max_x - min_x) * (max_y - min_y);
}
double ternarySearch(const int n) {
double lo = .0, hi = 3 * asin(.5);
for (int i = 0; i < 100; i += 1) {
const double thirdLength = (hi - lo) * 0.33333333333333333333;
double phi_1 = lo + thirdLength;
double phi_2 = hi - thirdLength;
if (retangleArea(phi_1, n) < retangleArea(phi_2, n)) {
hi = phi_2;
} else {
lo = phi_1;
}
}
return lo;
}
int main() {
ifstream fin("rubarba.in");
ofstream fout("rubarba.out");
fin.tie(0);
ios_base::sync_with_stdio(false);
int n; fin >> n;
for (int i = 0; i < n; i += 1) {
fin >> V[i].first >> V[i].second;
}
fout.setf(ios::fixed, ios::floatfield);
fout.precision(2);
fout << retangleArea(ternarySearch(n), n) << '\n';
fout.close();
return 0;
}