Cod sursa(job #1411621)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 31 martie 2015 20:48:05
Problema Camera Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.27 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

#define NMAX 2005
#define eps 1e-6
#define inf 200000.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)
        return ;

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

    if (!aux_size || p != aux[aux_size])
        aux[++ aux_size] = p;

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

    if (!aux_size || q != aux[aux_size])
        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);
}

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
    cout << fixed << setprecision(6) << area(kernel, kernel_size) << '\n';

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