Cod sursa(job #2012043)

Utilizator mariusn01Marius Nicoli mariusn01 Data 17 august 2017 17:56:12
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.46 kb
#include <fstream>
#include <iomanip>
#include <iostream>

#define DIM 10010
#define AXMAX 100010
#define x first
#define y second
#define eps 0.000001

using namespace std;

struct segment {
    double x1;
    double y1;
    double x2;
    double y2;

    segment () {
    }

    segment(pair<double, double> a, pair<double, double> b) {
        x1 = a.x;
        y1 = a.y;
        x2 = b.x;
        y2 = b.y;
    }

};

pair<double, double> v[DIM], aux, p[DIM], w[DIM];
int n, i, m, k, j, t, nexti, nextk;
double sol;

double det(double X1, double Y1, double X2, double Y2, double X3, double Y3) {
    return (X2-X1)*(Y3-Y1) - (X3-X1)*(Y2-Y1);
}

int egal(double x, double y) {
    double dif = x - y;
    if (dif >= -eps && dif <= eps) {
        return 1;
    } else {
        return 0;
    }
}

int Next(int i, int n) {
    if (i < n)
        return i+1;
    else
        return 1;
}



double modul(double x) {
    if (x < 0)
        return -x;
    else
        return x;
}

pair<double, double> intersectie(segment a, segment b) {
    double A1 = a.y2 - a.y1;
    double B1 = a.x1 - a.x2;
    double C1 = a.y1 * (a.x2 - a.x1) - a.x1 * (a.y2 - a.y1);

    double A2 = b.y2 - b.y1;
    double B2 = b.x1 - b.x2;
    double C2 = b.y1 * (b.x2 - b.x1) - b.x1 * (b.y2 - b.y1);

    double x = (double)(B1*C2 - B2*C1) * 1.0 / (B2*A1 - B1*A2);
    double y = (double)(A1*C2 - A2*C1) * 1.0 / (A2*B1 - A1*B2);

    return make_pair(x, y);
}

int semn(int i, int j, int k) {
    double r = det(v[i].x, v[i].y, v[j].x, v[j].y, p[k].x, p[k].y);
    if (egal(r, 0))
        return 0;
    if (r < 0)
        return -1;
    return 1;
}

int main () {
    ifstream fin ("camera.in");
    ofstream fout("camera.out");

///    cout<<det(0,0,1,0,1,1);

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

    }

    for (int i=1;i<=n;i++)
        sol += det(0, 0, v[i].x, v[i].y, v[Next(i, n)].x, v[Next(i, n)].y);


    double ax;
    if (sol < 0) {
        for (int i=2, j=n; i<j; i++,j--) {
            aux = v[i];
            v[i] = v[j];
            v[j] = aux;
        }
    }

    p[1] = make_pair(-AXMAX, -AXMAX);
    p[2] = make_pair(AXMAX, -AXMAX);
    p[3] = make_pair(AXMAX, AXMAX);
    p[4] = make_pair(-AXMAX, AXMAX);
    m = 4;

    for (i=1;i<=n;i++) {
        /// intersectez cu latura i, i+1 a poligonului dat
        nexti = Next(i, n);

        for (j=1;j<=m;j++)
            if (det(v[i].x, v[i].y, v[nexti].x, v[nexti].y, p[j].x, p[j].y) > 0) {
                break;
            }

        if (j == m+1) {
            fout<<0;
            return 0;
        }

        t = 0;
        //w[t] = p[j];

        k = j;
        do {
            nextk = Next(k, m);

            if (semn(i, nexti, k) > 0) {
                if (semn(i, nexti, nextk) > 0)
                    w[++t] = p[nextk];
                else
                    if (semn(i, nexti, nextk) == 0)
                        w[++t] = p[nextk];
                    else {
                        segment a(v[i], v[nexti]);
                        segment b(p[k], p[nextk]);
                        pair<double, double> r = intersectie(a, b);
                        w[++t] = r;
                    }
            }

            if (semn(i, nexti, k) == 0) {
                if (semn(i, nexti, nextk) > 0)
                    w[++t] = p[nextk];
                else
                    if (semn(i, nexti, nextk) == 0)
                        w[++t] = p[nextk];
            }

            if (semn(i, nexti, k) < 0) {
                if (semn(i, nexti, nextk) > 0) {
                    segment a(v[i], v[nexti]);
                    segment b(p[k], p[nextk]);
                    pair<double, double> r = intersectie(a, b);
                    w[++t] = r;
                    w[++t] = p[nextk];
                } else
                    if (semn(i, nexti, nextk) == 0)
                        w[++t] = p[nextk];
            }

            k = nextk;
        } while (k != j);

        m = t;
        for (j=1;j<=t;j++)
            p[j] = w[j];
/*
        cout<<m<<"\n";
        for (j=1;j<=m;j++) {
            cout<<p[j].x<<" "<<p[j].y<<"\n";
        }
        cout<<"\n";
*/
    }
    sol = 0;
    for (int i=1;i<=m;i++)
        sol += det(0, 0, p[i].x, p[i].y, p[Next(i, m)].x, p[Next(i, m)].y);
    if (sol < 0)
        sol = -sol;

    fout<<setprecision(2)<<fixed<<sol/2;

    return 0;
}