Cod sursa(job #913947)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 13 martie 2013 20:56:20
Problema Rubarba Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.47 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, pct;
int st[MAX * 2], ind[MAX * 2];
bool inStack[MAX];
double parallel, horizontal, ans;
PII V[MAX], aux[MAX];

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

bool cmp(const int &A, const int &B) {
    return  (V[A].x - V[pct].x) * (V[B].y - V[pct].y) <
            (V[B].x - V[pct].x) * (V[A].y - V[pct].y);
}

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));
}

inline long long dist(const PII &A, const PII &B) {
    long long dX = A.x - B.x, dY = A.y - B.y;
    return dX * dX + dY * dY;
}

void convexHull() {
    for(int i = 1; i <= N; i++)
        if(i != pct) ind[++ind[0]] = i;
    sort(ind + 1, ind + ind[0] + 1, cmp);
    st[st[0] = 1] = pct;
    for(int i = 1; i <= ind[0]; i++)
        while(st[0] >= 2 &&
              crossProduct(V[st[st[0] - 1]], V[st[st[0]]], V[ind[i]])) st[0]--;
    st[++st[0]] = pct;
    for(int i = st[0]; i > 1; i--) aux[i] = V[st[i]];
    for(int i = st[0]; i > 1; i--) V[N + 1 - i] = aux[i];
    N = st[0] - 1;
}

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;
}