Cod sursa(job #1338278)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 9 februarie 2015 22:10:23
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 kb
# include <algorithm>
# include <cstdio>
# include <cmath>
# include <vector>
using namespace std;

# define x first
# define y second
# define pb push_back
# define mp make_pair

typedef double db;
typedef pair <int, int> pr;
typedef pair <db, db> PR;
const char *FIN = "camera.in", *FOU = "camera.out";
const int MAX = 2005;
const db eps = 1e-6, oo = 1e+6;

pr V[MAX];
vector <PR> vec, nextt;
vector <int> aux;
int N;

inline int semn (pair <db, PR> Cf, PR XY) {
    db Z = Cf.x * XY.x + Cf.y.x * XY.y + Cf.y.y;
    return (Z < -eps ? -1 : (Z > eps ? 1 : 0));
}

inline pair <db, PR> get_coef (PR A, PR B) {
    return mp (A.y - B.y, mp (B.x - A.x, A.x * B.y - B.x * A.y));
}

inline PR intersect (pair <db, PR> Cf, PR X, PR Y) {
    pair <db, PR> XX = get_coef (X, Y);
    double determin = Cf.x * XX.y.x - XX.x * Cf.y.x;
    if (fabs (determin) < eps)
        return mp (-oo, -oo);
    return mp ((Cf.y.x * XX.y.y - XX.y.x * Cf.y.y) / determin, (XX.x * Cf.y.y - Cf.x * XX.y.y) / determin);
}

inline db get_sol (void) {
    vec.clear (), aux.clear ();
    vec.pb (mp (-oo, -oo));
    vec.pb (mp (-oo, +oo));
    vec.pb (mp (+oo, +oo));
    vec.pb (mp (+oo, -oo));
    for (int i = 0; i < N; ++i, vec = nextt) {
        nextt.clear (), aux.resize (vec.size () + 1);
        pair <db, PR> Cf = get_coef (V[i], V[i + 1]);
        for (size_t j = 0; j < vec.size (); ++j)
            aux[j] = semn (Cf, vec[j]);
        aux[vec.size ()] = aux[0];
        for (size_t j = 0, k = vec.size (); j < k; ++j) {
            PR AUX = vec[ (j + 1) % static_cast <int> (vec.size ()) ];
            if (aux[j] <= 0 && aux[j + 1] <= 0)
                nextt.pb (AUX);
            if (aux[j] <= 0 && aux[j + 1] >  0)
                nextt.pb (intersect (Cf, vec[j], AUX));
            if (aux[j] >  0 && aux[j + 1] <= 0) {
                nextt.pb (intersect (Cf, vec[j], AUX));
                nextt.pb (AUX);
            }
        }
    }
    double sol = 0;
    vec.pb (vec[0]);
    for (size_t i = 0, j = vec.size (); i + 1 < j; ++i)
        sol += vec[i].x * vec[i + 1].y - vec[i + 1].x * vec[i].y;
    return fabs (sol * 0.5);
}

int main (void) {
    freopen (FIN, "r", stdin);

    scanf ("%d", &N);
    for (int i = 0; i < N; ++i)
        scanf ("%d %d", &V[i].x, &V[i].y);
    V[N] = V[0];
    double sol = get_sol ();
    if (fabs (sol) < eps) {
        reverse (V, V + N + 1);
        sol = get_sol ();
    }
    fprintf (fopen (FOU, "w"), "%.2lf", sol);
}