Cod sursa(job #960498)

Utilizator primulDarie Sergiu primul Data 10 iunie 2013 16:40:55
Problema Camera Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.15 kb
#include <cmath>
#include <fstream>
#include <iomanip>
#include <algorithm>
 
using namespace std;
 
const int RINF = 0x3f3f3f3f;
const int INF = 100002;
const double eps = 1e-6;
 
int N, M, P;
double X[2002], Y[2002];
double Xn[2002], Yn[2002];
double Xs[2002], Ys[2002];
 
inline bool same(double px1, double py1, double px2, double py2)
{
    int samex = (fabs(px1 - px2) < eps);
    int samey = (fabs(py1 - py2) < eps);
 
    return samex == 1 && samey == 1;
}
inline pair<double, double> intersect(double px1, double py1, double px2, double py2, double px3, double py3, double px4, double py4)
{
    double a1 = py1 - py2, b1 = px2 - px1, c1 = px1 * py2 - px2 * py1;
    double a2 = py3 - py4, b2 = px4 - px3, c2 = px3 * py4 - px4 * py3;
 
    if (a1 * b2 == a2 * b1) return make_pair(RINF, RINF);
 
    double yn = (a2 * c1 - a1 * c2) / (a1 * b2 - a2 * b1);
    double xn;
 
    if (a1 > -eps && a1 < eps) xn = (- b2 * yn - c2) / a2;
    else                       xn = (- b1 * yn - c1) / a1;
 
    if (xn - min(px3, px4) > -eps && xn - max(px3, px4) < eps && yn - min(py3, py4) > -eps && yn - max(py3, py4) < eps)
        if (!same(xn, yn, px3, py3) && !same(xn, yn, px4, py4))
            return make_pair(xn, yn);
    return make_pair(RINF, RINF);
}
inline double turn(double px1, double py1, double px2, double py2, double px3, double py3)
{
    return px1 * py2 + px2 * py3 + px3 * py1 - py1 * px2 - py2 * px3 - py3 * px1;
}
inline double area(double pX[], double pY[], int N)
{
    double resnow = 0;
    for (int i = 1; i <= N; ++i)
        resnow += pX[i] * pY[i + 1] - pY[i] * pX[i + 1];
    return resnow / 2;
}
inline int sign(double x)
{
    if (x > -eps && x < eps) return 0;
    if (x < 0) return -1;
    return 1;
}
 
int main()
{
    ifstream fin("camera.in");
    ofstream fout("camera.out");
 
    fin >> N;
    for (int i = 1; i <= N; ++i)
        fin >> X[i] >> Y[i];
    X[N + 1] = X[1], Y[N + 1] = Y[1];
 
    M = 4;
    Xn[1] = -INF, Yn[1] = -INF;
    Xn[2] = -INF, Yn[2] = INF;
    Xn[3] = INF, Yn[3] = INF;
    Xn[4] = INF, Yn[4] = -INF;
    Xn[5] = Xn[1], Yn[5] = Yn[1];
 
    int signneed = sign(area(X, Y, N));
    for (int i = 1; i <= N; ++i) // muchia i
    {
        P = 0;
        for (int j = 1; j <= M; ++j)
        {
            pair<double, double> now = intersect(X[i], Y[i], X[i + 1], Y[i + 1], Xn[j], Yn[j], Xn[j + 1], Yn[j + 1]);
            if (now.first != RINF)
            {
                ++P;
                Xs[P] = now.first;
                Ys[P] = now.second;
            }
            if (sign(turn(X[i], Y[i], X[i + 1], Y[i + 1], Xn[j + 1], Yn[j + 1])) == signneed || sign(turn(X[i], Y[i], X[i + 1], Y[i + 1], Xn[j + 1], Yn[j + 1])) == 0)
            {
                ++P;
                Xs[P] = Xn[j + 1];
                Ys[P] = Yn[j + 1];
            }
        }
 
        M = P;
        for (int j = 1; j <= M; ++j)
        {
            Xn[j] = Xs[j];
            Yn[j] = Ys[j];
        }
        Xn[M + 1] = Xn[1], Yn[M + 1] = Yn[1];
    }
 
    fout << fixed << setprecision(2) << fabs(area(Xn, Yn, M)) << '\n';
 
    fin.close();
    fout.close();
}