Cod sursa(job #600895)

Utilizator SpiderManSimoiu Robert SpiderMan Data 4 iulie 2011 00:18:02
Problema Camera Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.45 kb
# 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];
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));
}

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

db get_sol (void) {
    vector <PR> vec;
    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) {
        vector <PR> next;
        vector <int> aux (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; j < vec.size (); ++j) {
            PR AUX = vec[ (j + 1) % static_cast <int> (vec.size ()) ];
            if (aux[j] <= 0 && aux[j + 1] <= 0)
                next.pb (AUX);
            if (aux[j] <= 0 && aux[j + 1] >  0)
                next.pb (intersect (Cf, vec[j], AUX));
            if (aux[j] >  0 && aux[j + 1] <= 0) {
                next.pb (intersect (Cf, vec[j], AUX));
                next.pb (AUX);
            }
        }
        vec = next;
    }
    double sol = 0;
    vec.pb (vec[0]);
    for (size_t i = 0; i + 1 < vec.size (); ++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) {
        for (int i = 0, j = N; i < j; ++i, --j)
            swap (V[i], V[j]);
        sol = get_sol ();
    }
    fprintf (fopen (FOU, "w"), "%.2lf", sol);
}