Cod sursa(job #1724004)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 1 iulie 2016 23:51:34
Problema Rubarba Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <fstream>
#include <cmath>
#include <algorithm>

using namespace std;

#define double long double

constexpr int MAX_N = 100000;
constexpr double EPS = 1e-17;

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 mid = (lo + hi) * .5;
        if (retangleArea(mid, n) > retangleArea(mid + EPS, n)) {
            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;
    }
    fout.setf(ios::fixed, ios::floatfield);
    fout.precision(2);
    fout << retangleArea(ternarySearch(n), n) << '\n';
    fout.close();
    return 0;
}