Cod sursa(job #1112796)

Utilizator Theorytheo .c Theory Data 20 februarie 2014 00:34:25
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <fstream>
#include <cmath>
#include <iomanip>

using namespace std;

#define point pair <double, double>
#define x first
#define y second

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

const double eps = 0.0000001;
const double INF = 100100;
const int NMAX  = 2010;

point V[NMAX]; int N; point curPol[NMAX * 2];point Pol[NMAX * 2]; int curCnt; int Cnt;

void read() {

    fin >> N;
    for(int i = 1; i <= N; ++i) {

        double a, b; fin >> a >> b;
        V[i] = make_pair(a, b);
    }
    V[N + 1] = V[1];
}

int sarrus(point A, point B, point C) {

    double a = A.y - B.y;
    double b = B.x - A.x;
    double c = A.x * B.y - A.y * B.x;

    if(a * C.x + b * C.y + c > eps)
        return 1;
    return -1;
}

double det(double A, double B, double C, double D) {

    return A * D - C * B;
}

point intersection(point A, point B, point C, point D) {

    double a1 = A.y - B.y ; double b1 = B.x - A.x; double c1 = -A.x * B.y + A.y * B.x;
    double a2 = C.y - D.y ; double b2 = D.x - C.x; double c2 = -C.x * D.y + C.y * D.x;

    double newX = det(c1, b1, c2, b2) / det(a1, b1, a2, b2);
    double newY = det(a1, c1, a2, c2) / det(a1, b1, a2, b2);

    return make_pair(newX, newY);
}


double solve(int sgn) {

// == sgn => interior

    Cnt = 4;
    Pol[1] = make_pair(INF, -INF);
    Pol[2] = make_pair(INF, INF);
    Pol[3] = make_pair(-INF, INF);
    Pol[4] = make_pair(-INF, -INF);
    Pol[5] = Pol[1];

    for(int i = 1; i <= N; ++i) {

        curCnt = 0;
        for(int j = 1; j <= Cnt; ++j) {

            if(sarrus(V[i], V[i + 1], Pol[j]) == sgn) {
                curPol[++curCnt] = Pol[j];

                if(sarrus(V[i], V[i + 1], Pol[j + 1]) != sgn)
                    curPol[++curCnt] = intersection(V[i], V[i + 1], Pol[j], Pol[j + 1]);
            } else if(sarrus(V[i], V[i + 1], Pol[j + 1]) == sgn)
                    curPol[++curCnt] = intersection(V[i], V[i + 1], Pol[j], Pol[j + 1]);
        }

        if(curCnt == 0) return 0;

        for(int j = 1; j <= curCnt; ++j)
            Pol[j] = curPol[j];
        Pol[curCnt + 1] = Pol[1];
        Cnt = curCnt;
    }

    double area = 0;

    for(int i = 1; i <= Cnt; ++i) {
        area += Pol[i].x * Pol[i + 1].y - Pol[i + 1].x * Pol[i].y;
    }

    if(area < 0) area = -area;

    return area * 0.5;


}

int main() {

    read();
    fout << fixed;
    fout <<setprecision(2) <<  max(solve(1), solve(-1));

    return 0;
}