Cod sursa(job #1094778)

Utilizator toranagahVlad Badelita toranagah Data 29 ianuarie 2014 20:29:45
Problema Rubarba Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.2 kb
#include <cmath>
#include <cstdint>
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

ifstream fin("rubarba.in");
ofstream fout("rubarba.out");

#define x first
#define y second
typedef pair<int, int> Point;

const int MAX_N = 100100;

struct Line {
    int64_t a, b, c;

    Line(int64_t aa=0, int64_t bb=0, int64_t cc=0)
        : a(aa), b(bb), c(cc) {}
    Line(const Point &p1, const Point &p2) {
        a = 1LL * p2.y - p1.y;
        b = 1LL * p1.x - p2.x;
        c = 1LL * a * p1.x + b * p1.y;
    }
};

int N;
Point points[MAX_N];
Point hull[MAX_N];
int M = 0;
double result;

void read_input();
void solve();
void print_output();
void convex_hull();
int64_t cross_product(const Point &a, const Point &b, const Point &o);
double calc_area(const Line &l, int opp, int side1, int side2);
int get_opposite(const Line &l, int last);
int get_side1(const Line &l, int last);
int get_side2(const Line &l, int last);
Line get90(const Line &l, const Point &p);
Line get180(const Line &l, const Point &p);
double dist(const Line &l, const Point &p);
int next(int i, int n);
int prev(int i, int n);

inline void prtl(const Line &l) {
    cerr << l.a << "x + " << l.b << "y = " << l.c << endl;
}

int main() {
    read_input();
    solve();
    print_output();
    return 0;
}

void read_input() {
    fin >> N;
    for (int i = 1; i <= N; i += 1) {
        fin >> points[i].x >> points[i].y;
    }
}

void solve() {
    convex_hull();

    int start = 1;
    Line l(hull[start], hull[next(start, M)]);
    int opp = get_opposite(l, next(start, M));
    int side1 = get_side1(l, start);
    int side2 = get_side2(l, opp);

    result = calc_area(l, opp, side1, side2);
    for (start = 2; start <= M; start += 1) {
        l = Line(hull[start], hull[next(start, M)]);
        opp = get_opposite(l, opp);
        side1 = get_side1(l, side1);
        side2 = get_side2(l, side2);
        result = min(result, calc_area(l, opp, side1, side2));
    }
}

void print_output() {
    fout << result;
}

int get_opposite(const Line &l, int last=1) {
    int64_t d = get180(l, hull[last]).c;
    for (int i = next(last, M); i != last; i = next(i, M)) {
        int64_t dd = get180(l, hull[i]).c;

        if (abs(dd - l.c) > abs(d - l.c)) d = dd;
        else return prev(i, M);
    }
    return -1;
}

int get_side1(const Line &l, int last) {
    int64_t d = get90(l, hull[last]).c;
    for (int i = next(last, M); i != last; i = next(i, M)) {
        int64_t dd = get90(l, hull[i]).c;
        if (dd > d) d = dd;
        else return prev(i, M);
    }
    return -1;
}

int get_side2(const Line &l, int last) {
    int64_t d = get90(l, hull[last]).c;
    for (int i = next(last, M); i != last; i = next(i, M)) {
        int64_t dd = get90(l, hull[i]).c;
        if (dd < d) d = dd;
        else return prev(i, M);
    }
    return -1;
}

void convex_hull() {
    int minp = 1;
    for (int i = 2; i <= N; i += 1) {
        if (points[i] < points[minp]) {
            minp = i;
        }
    }
    Point lowest = points[minp];
    swap(points[1], points[minp]);
    auto cmp = [lowest](const Point &p1, const Point &p2) {
        return (cross_product(p1, p2, lowest) < 0);
    };
    sort(points + 2, points + N + 1, cmp);

    hull[++M] = points[1];
    hull[++M] = points[2];
    for (int i = 3; i <= N; i += 1) {
        while (M >= 2 && cross_product(hull[M], points[i], hull[M - 1]) > 0) M -= 1;
        hull[++M] = points[i];
    }
}

inline double dist(const Line &l, const Point &p) {
    return abs((1.0 * l.a * p.x + 1.0 * l.b * p.y - 1.0 * l.c) / sqrt(1.0 * l.a * l.a + 1.0 * l.b * l.b));
}

inline double calc_area(const Line &l, int opp, int side1, int side2) {
    return dist(l, hull[opp]) * dist(get90(l, hull[side1]), hull[side2]);
}

inline int64_t cross_product(const Point &a, const Point &b, const Point &o) {
    return 1LL * (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

inline Line get90(const Line &l, const Point &p) {
    return Line(-l.b, l.a, (-l.b * p.x) + (l.a * p.y));
}

inline Line get180(const Line &l, const Point &p) {
    return Line(l.a, l.b, (l.a * p.x) + (l.b * p.y));
}

inline int next(int i, int n) {
    return (i >= n ? 1 : i + 1);
}

inline int prev(int i, int n) {
    return (i <= 1 ? n : i - 1);
}