Cod sursa(job #1412428)

Utilizator danalex97Dan H Alexandru danalex97 Data 1 aprilie 2015 11:59:33
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.87 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>

#define NMAX 2005
#define eps 1e-6
#define inf 1000010.0

using namespace std;

struct point {
    double x, y;

    point (double x = 0, double y = 0): x(x), y(y) {}

    bool operator== (const point &b) const {
        return (fabs(x - b.x) <= eps && fabs(y - b.y) <= eps);
    }

    bool operator!= (const point &b) const {
        return (fabs(x - b.x) > eps || fabs(y - b.y) > eps);
    }
} v[NMAX];

inline double ccw (const point &a, const point &b, const point &c) {
    return ((a.x - b.x) * (c.y - b.y) - (a.y - b.y) * (c.x - b.x));
}

inline double area (const point &a, const point &b) {
    return (a.x * b.y - a.y * b.x);
}

point intersection (const point &a, const point &b, const point &c, const point &d) { //AB intersects [CD]
    double A1 = b.y - a.y;
    double B1 = a.x - b.x;
    double C1 = a.y * b.x - a.x * b.y;

    double A2 = d.y - c.y;
    double B2 = c.x - d.x;
    double C2 = c.y * d.x - c.x * d.y;

    if (fabs(A1 * B2 - A2 * B1) <= eps)
        return point(inf, inf);

    point p = point((C2 * B1 - C1 * B2) / (A1 * B2 - A2 * B1), (C2 * A1 - C1 * A2) / (A2 * B1 - A1 * B2));

    if (min(c.x, d.x) <= p.x + eps && p.x <= max(c.x, d.x) + eps && min(c.y, d.y) <= p.y + eps && p.y <= max(c.y, d.y) + eps)
        return p;
    return point(inf, inf);
}

int kernel_size;
point kernel[NMAX];
point aux[NMAX];

inline void _copy (point *to, point *from, int n) {
    for (int i = 1; i <= n; i++)
        to[i] = from[i];
}

double area (point *v, int n) {
    if (!n)
        return 0;

    double ans = area(v[n], v[1]);
    for (int i = 1; i < n; i++)
        ans += area(v[i], v[i + 1]);

    return (ans * 0.5);
}

inline void add_halfplane (const point &a, const point &b) { //From a to b
    if (!kernel_size) {
    //    cout << "GOL" << endl;
        return ;
    }

    //cout << "Semiplan " << endl;
    //cout << a.x << ' ' << a.y << endl;
    //cout << b.x << ' ' << b.y << endl;
    //cout << endl;

    int i, j;
    point p, q;

    for (i = 1; i <= kernel_size; i++) {
        p = intersection(a, b, kernel[i], kernel[i % kernel_size + 1]);

        if (fabs(p.x - inf) >= eps)
            break;
    }

    if (i == kernel_size + 1) {
        if (ccw(a, b, kernel[1]) >= -eps) {
            kernel_size = 0;
        }
        return ;
    }

    for (j = kernel_size - (p == kernel[1]); j > i; j--) {
        q = intersection(a, b, kernel[j], kernel[j % kernel_size + 1]);

        if (fabs(q.x - inf) >= eps)
            break;
    }

    if (p == q) {
        if (ccw(a, b, kernel[1]) >= -eps) {
            kernel_size = 0;
        }
        return ;
    }

    int i1 = i;
    int i2 = j;

    //Deci avem de sters laturile i si j si sa adaugam
    int aux_size = 0;
    for (i = 1; i <= i1; i++)
        if (ccw(a, b, kernel[i]) < eps)
            aux[++ aux_size] = kernel[i];

    aux[++ aux_size] = p;

    for (; i <= i2; i++)
        if (ccw(a, b, kernel[i]) < eps)
            aux[++ aux_size] = kernel[i];

    aux[++ aux_size] = q;

    for (; i <= kernel_size; i++)
        if (ccw(a, b, kernel[i]) < eps)
            aux[++ aux_size] = kernel[i];

    kernel_size = aux_size;
    _copy(kernel, aux, kernel_size);

    aux_size = 0;
    for (int i = 1; i <= kernel_size; i++)
        if (kernel[i] != kernel[i % kernel_size + 1])
            aux[++ aux_size] = kernel[i];

    kernel_size = aux_size;
    _copy(kernel, aux, kernel_size);

    //cout << kernel_size << endl;
    //for (int i = 1; i <= kernel_size; i++)
    //    cout << kernel[i].x << ' ' << kernel[i].y << endl;
    //cout << "deci da" << endl;
}

int main()
{
    ifstream cin("camera.in");
    ofstream cout("camera.out");

    int n = 0;
    cin >> n;

    double min_x = inf;
    double min_y = inf;
    double max_x = -inf;
    double max_y = -inf;

    for (int i = 1; i <= n; i++) {
        cin >> v[i].x >> v[i].y;

        min_x = min(min_x, v[i].x);
        min_y = min(min_y, v[i].y);
        max_x = max(max_x, v[i].x);
        max_y = max(max_y, v[i].y);
    }

    if (area(v, n) <= eps)
        reverse(v + 1, v + n + 1);

    kernel[++ kernel_size] = point(min_x, min_y);
    kernel[++ kernel_size] = point(max_x, min_y);
    kernel[++ kernel_size] = point(max_x, max_y);
    kernel[++ kernel_size] = point(min_x, max_y);

    for (int i = 1; i <= n; i++)
        add_halfplane(v[i], v[i % n + 1]);

    //cout << kernel_size << endl;
    //for (int i = 1; i <= kernel_size; i++)
    //    cout << kernel[i].x << ' ' << kernel[i].y << endl;

    //De vazut mai bine cazul cand aria e nula
    //assert(area(kernel, kernel_size) > eps);

    cout << fixed << setprecision(2) << area(kernel, kernel_size) << '\n';

    cin.close();
    cout.close();
    return 0;
}