Pagini recente » Cod sursa (job #1990272) | Cod sursa (job #3031568) | Cod sursa (job #2190618) | Cod sursa (job #1026140) | Cod sursa (job #1723999)
#include <fstream>
#include <cmath>
#include <algorithm>
using namespace std;
#define double long double
constexpr int MAX_N = 100000;
constexpr double EPS = 1e-18;
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);
while (hi - lo > EPS) {
const double mid = (lo + hi) * .5;
if (retangleArea(mid, n) - retangleArea(mid + EPS, n) > EPS) {
lo = mid;
} else {
hi = mid;
}
}
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;
}
random_shuffle(V, V + n);
fout.setf(ios::fixed, ios::floatfield);
fout.precision(2);
fout << retangleArea(ternarySearch(n), n) << '\n';
fout.close();
return 0;
}