Cod sursa(job #654827)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 30 decembrie 2011 23:33:08
Problema Camera Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.38 kb
#include <cstdio>
#include <vector>
#include <algorithm>

#define NMax 2005
#define pdd pair <double, double>
#define x first
#define y second
#define Infinity 2000000000
#define Precision 1e-7

using namespace std;

vector <pdd> InitP;
pdd Null;
int N;
double S;

void Read ()
{
    freopen ("camera.in", "r", stdin);
    scanf ("%d", &N);
    for (int i=1; i<=N; ++i)
    {
        pdd CurrentP;
        scanf ("%lf %lf", &CurrentP.x, &CurrentP.y);
        InitP.push_back (CurrentP);
    }
    InitP.push_back (InitP.front ());
    Null.x=Infinity+1;
    Null.y=Infinity+1;
}

inline bool Compare (pdd P1, pdd P2)
{
    if (-Precision<=P1.x-P2.x and P1.x-P2.x<=Precision)
    {
        if (-Precision<=P1.y-P2.y and P1.y-P2.y<=Precision)
        {
            return true;
        }
        return false;
    }
    return false;
}

inline void GetCoeficient (pdd P1, pdd P2, double &A, double &B, double &C)
{
    A=P2.y-P1.y;
    B=P1.x-P2.x;
    C=P2.x*P1.y-P1.x*P2.y;
}

inline int Sign (double A, double B, double C, pdd P)
{
    if (A*P.x+B*P.y+C>Precision)
    {
        return 1;
    }
    if (A*P.x+B*P.y+C<-Precision)
    {
        return -1;
    }
    return 0;
}

inline pdd Intersect (double A1, double B1, double C1, pdd P1, pdd P2)
{
    pdd I;
    double A2, B2, C2;
    GetCoeficient (P1, P2, A2, B2, C2);
    if (Sign (A1, B1, C1, P1)==Sign (A1, B1, C1, P2))
    {
        return Null;
    }
    I.x=(C1*B2-C2*B1)/(B1*A2-B2*A1);
    I.y=(C2*A1-C1*A2)/(B1*A2-B2*A1);
    return I;
}

vector <pdd> Polygon (double A, double B, double C, vector <pdd> &P)
{
    vector <pdd> NewP;
    for (unsigned i=0; i+1<P.size (); ++i)
    {
        if (Sign (A, B, C, P[i])>=0)
        {
            if (NewP.empty ())
            {
                NewP.push_back (P[i]);
            }
            if (!Compare (P[i], NewP.back ()))
            {
                NewP.push_back (P[i]);
            }
        }
        pdd I=Intersect (A, B, C, P[i], P[i+1]);
        if (I!=Null)
        {
            if (NewP.empty ())
            {
                NewP.push_back (I);
            }
            if (!Compare (I, NewP.back ()))
            {
                NewP.push_back (I);
            }
            NewP.push_back (I);
        }
    }
    if (!NewP.empty ())
    {
        NewP.push_back (NewP.front ());
    }
    return NewP;
}

inline double GetArea (vector <pdd> P)
{
    double Area=0;
    for (int i=0; i+1<P.size (); ++i)
    {
        Area+=(P[i].x*P[i+1].y-P[i].y*P[i+1].x);
    }
    Area*=0.5;
    if (Area<0)
    {
        Area=-Area;
    }
    return Area;
}

double Solve ()
{
    vector <pdd> P;
    P.push_back (make_pair (-Infinity, -Infinity));
    P.push_back (make_pair (-Infinity, Infinity));
    P.push_back (make_pair (Infinity, Infinity));
    P.push_back (make_pair (Infinity, -Infinity));
    P.push_back (P.front ());
    for (int i=0; i<N; ++i)
    {
        double A, B, C;
        GetCoeficient(InitP[i], InitP[i+1], A, B, C);
        P=Polygon (A, B, C, P);
    }
     return GetArea (P);
}

void Print ()
{
    freopen ("camera.out", "w", stdout);
    printf ("%.2lf\n", S);
}

int main()
{
    Read ();
    S=Solve ();
    if (S<Precision)
    {
        reverse (InitP.begin (), InitP.end ());
        S=Solve ();
    }
    Print ();
    return 0;
}