Cod sursa(job #911366)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 11 martie 2013 16:14:14
Problema Rubarba Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.06 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>

#define MAX 100005
#define PII pair<int, int>
#define x first
#define y second

using namespace std;

int N;
int st[MAX];
bool inStack[MAX];
double parallel, horizontal, ans;
PII V[MAX], aux[MAX];

void citire() {
    ifstream in("rubarba.in");
    in>>N;
    for(int i = 1; i <= N; i++) in>>V[i].x>>V[i].y;
    in.close();
}

inline long long crossProduct(PII O, PII A, PII B) {
    return  (1LL * (A.x - O.x)) * (1LL * (B.y - O.y)) -
            (1LL * (B.x - O.x)) * (1LL * (A.y - O.y));
}

inline long long dotProduct(PII O, PII A, PII B) {
    return  (1LL * (A.x - O.x)) * (1LL * (B.x - O.x)) +
            (1LL * (A.y - O.y)) * (1LL * (B.y - O.y));
}

void convexHull() {
    sort(V + 1, V + N + 1);
    st[++st[0]] = 1, st[++st[0]] = 2;
    inStack[2] = true;
    for(int i = 1, p = 1; i > 0; i += (p = (i == N ? -p : p))) {
        if(inStack[i]) continue;
        while(st[0] >= 2 && crossProduct(V[st[st[0] - 1]], V[st[st[0]]], V[i]) <= 0LL)
            inStack[st[st[0]--]] = false;
        st[++st[0]] = i;
        inStack[i] = true;
    }
    for(N = 1; N < st[0]; N++) aux[N] = V[st[N]];
    N--;
    for(int i = 1; i <= N; i++) V[i] = aux[i];
}

inline int next(int val) {
    if(val == N) return 1;
    return val + 1;
}

inline PII getVector(const PII &A, const PII &B) {
    PII result;
    result.x = B.x - A.x, result.y = B.y - A.y;
    return result;
}

double getParallelDistance(const PII &A, const PII &B, const double M) {
    return fabs((1.0 * A.y - M * A.x) - (1.0 * B.y - M * B.x)) / sqrt(M * M + 1.0);
}

void getMinimumAreaEnclosingRectangle() {
    int i, j = 1, k, m;
    PII O;
    O.x = O.y = 0;
    for(i = 1; i <= N; i++) {
        while(dotProduct(O, getVector(V[i], V[next(i)]), getVector(V[j], V[next(j)])) >= 0LL)
            j = next(j);
        if(i == 1) k = j;
        while(crossProduct(O, getVector(V[i], V[next(i)]), getVector(V[k], V[next(k)])) >= 0LL)
            k = next(k);
        if(i == 1) m = k;
        while(dotProduct(O, getVector(V[i], V[next(i)]), getVector(V[m], V[next(m)])) <= 0LL)
            m = next(m);
        if(V[i].x == V[next(i)].x) {
            parallel = fabs(V[k].x - V[i].x);
            horizontal = fabs(V[m].y - V[j].y);
        } else if(V[i].y == V[next(i)].y) {
            parallel = fabs(V[k].y - V[i].y);
            horizontal = fabs(V[m].x - V[j].x);
        } else {
            double slope = (1.0 * (V[next(i)].y - V[i].y)) / (1.0 * (V[next(i)].x - V[i].x));
            parallel = getParallelDistance(V[i], V[k], slope);
            horizontal = getParallelDistance(V[j], V[m], -1.0 / slope);
        }
        double area = parallel * horizontal;
        if(i == 1 || area < ans)
            ans = area;
    }
}

void afisare() {
    ofstream out("rubarba.out");
    out<<fixed<<setprecision(2)<<ans;
}

int main()
{
    citire();
    if(N > 2) {
        convexHull();
        getMinimumAreaEnclosingRectangle();
    }
    afisare();
    return 0;
}