Cod sursa(job #3158866)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 19 octombrie 2023 22:27:18
Problema Rubarba Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.72 kb
#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 100000;
const long double EPS = 1e-9;
using ll = long long;
using d64 = long double;

struct Point {
    d64 x, y;
    bool operator<(const Point &oth) const {
        if(x == oth.x) {
            return y < oth.y;
        }
        return x < oth.x;
    }
};

int N;
vector <Point> P;

int cp(Point a, Point b, Point c) {
    d64 t = 1ll * (c.y - a.y) * (b.x - a.x) - (b.y - a.y) * (c.x - a.x);

    if(abs(t) < EPS) {
        return 0;
    }

    return t < 0 ? -1 : 1;
}

Point rotate(Point p, d64 angle) {
    return {p.x * cos(angle) - p.y * sin(angle), p.x * sin(angle) + p.y * cos(angle)};
} 

vector <Point> convex_hull(vector <Point> P) {
    sort(P.begin(), P.end());

    vector <Point> ret;
    for(int i = 0, t = 1; i >= 0; i += (t = (i == P.size() - 1 ? -t : t))) {
        while(ret.size() >= 2 && cp(ret[ret.size() - 2], ret.back(), P[i]) == 1) {
            ret.pop_back();
        }
        ret.push_back(P[i]);
    }
    
    return ret;
}

int get_max_x(vector <Point> &C, int index, d64 angle) {
    int ret;
    if(index == -1) {
        ret = 0;
        for(int i = 0; i < C.size() - 1; i++) {
            if(rotate(C[ret], angle).x < rotate(C[i], angle).x) {
                ret = i;
            }
        }
    }
    else {
        ret = index;
        while(true) {
            int i = (ret + 1) % (C.size() - 1);
            if(rotate(C[ret], angle).x < rotate(C[i], angle).x) {
                ret = i;
            }
            else {
                break;
            }
        }
    }

    return ret;
}

int get_min_x(vector <Point> &C, int index, d64 angle) {
    int ret;
    if(index == -1) {
        ret = 0;
        for(int i = 0; i < C.size() - 1; i++) {
            if(rotate(C[ret], angle).x > rotate(C[i], angle).x) {
                ret = i;
            }
        }
    }
    else {
        ret = index;
        while(true) {
            int i = (ret + 1) % (C.size() - 1);
            if(rotate(C[ret], angle).x > rotate(C[i], angle).x) {
                ret = i;
            }
            else {
                break;
            }
        }
    }

    return ret;
}

int get_min_y(vector <Point> &C, int index, d64 angle) {
    int ret;
    if(index == -1) {
        ret = 0;
        for(int i = 0; i < C.size() - 1; i++) {
            if(rotate(C[ret], angle).y > rotate(C[i], angle).y) {
                ret = i;
            }
        }
    }
    else {
        ret = index;
        while(true) {
            int i = (ret + 1) % (C.size() - 1);
            if(rotate(C[ret], angle).y > rotate(C[i], angle).y) {
                ret = i;
            }
            else {
                break;
            }
        }
    }

    return ret;
}

int main() {
#ifndef LOCAL
    freopen("rubarba.in", "r", stdin);
    freopen("rubarba.out", "w", stdout);
#endif


    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    P.resize(N);
    for(auto &p : P) {
        cin >> p.x >> p.y;
    }

    if(N <= 2) {
        cout << "0\n";
        return 0;
    }

    vector<Point> C = convex_hull(P);

    d64 ans = 1e13;
    int max_x = -1, min_x = -1, min_y = -1;
    for(int i = 0; i < C.size() - 1; i++) {
        d64 dy = C[i + 1].y - C[i].y;
        d64 dx = C[i + 1].x - C[i].x;
        d64 angle = -atan2(dy, dx);

        max_x = get_max_x(C, -1, angle);
        min_x = get_min_x(C, -1, angle);
        min_y = get_min_y(C, -1, angle);

        Point a = rotate(C[i], angle);
        Point b = rotate(C[max_x], angle);
        Point c = rotate(C[min_x], angle);
        Point d = rotate(C[min_y], angle);

        assert(d.y <= a.y && c.x <= b.x);
        ans = min(ans, (a.y - d.y) * (b.x - c.x));
    }

    cout << fixed << setprecision(2) << ans << "\n";
    return 0;
}