Cod sursa(job #1690328)

Utilizator GinguIonutGinguIonut GinguIonut Data 14 aprilie 2016 23:43:02
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.8 kb
#include <fstream>
#include <iomanip>
#include <cmath>

#define nMax 2002
#define pdd pair<double, double>
#define pddd pair<double, pair<double, double> >
#define x first
#define y second
#define A first
#define B second.first
#define C second.second
#define mkp make_pair
#define EPS 1e-6
#define INF 10000000

using namespace std;
ifstream fin("camera.in");
ofstream fout("camera.out");
int n, nr;
pdd Pct[nMax], Sol[2][2*nMax], Punct;
pddd ecdr, ecur;
void read()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>Pct[i].x>>Pct[i].y;

    Pct[n+1]=Pct[1];
}
pddd ec_dreapta(const pdd& a, const pdd& b)
{
    pddd sol;
    sol.A=b.y - a.y;
    sol.B=a.x - b.x;
    sol.C=(a.y * b.x) - (b.y * a.x);

    return sol;
}
double pct_semiplan(const pddd& ecdr, const pdd& punct)
{
    return ecdr.A * punct.x + ecdr.B * punct.y + ecdr.C;
}
void verif()
{
    double Arie=0;

    for(int i=1;i<=n;i++)
        Arie=Arie+(Pct[i].x * Pct[i+1].y) - (Pct[i].y * Pct[i+1].x);

    if(Arie<=-EPS)
    {
        for(int i=1;i<=n/2;i++)
            swap(Pct[i], Pct[n-i+1]);
        Pct[n+1]=Pct[1];
    }
}
pdd pct_intersectie(const pddd& ecdr, const pddd& ecur)
{
    pdd sol;

    sol.x=(ecur.B * ecdr.C - ecur.C * ecdr.B) / (ecdr.B * ecur.A - ecur.B * ecdr.A);
    sol.y=(ecur.A * ecdr.C - ecur.C * ecdr.A) / (ecur.B * ecdr.A - ecur.A * ecdr.B);

    return sol;
}
void solve()
{
    Sol[0][++nr]=mkp(-INF, -INF);
    Sol[0][++nr]=mkp(INF, -INF);
    Sol[0][++nr]=mkp(INF, INF);
    Sol[0][++nr]=mkp(-INF, INF);

    for(int i=1;i<=n;i++)
    {
        ecdr=ec_dreapta(Pct[i], Pct[i+1]);
        int nrnou=0;
        Sol[0][++nr]=Sol[0][1];
        for(int j=1;j<nr;j++)
        {
            ecur=ec_dreapta(Sol[0][j], Sol[0][j+1]);
            double f1=pct_semiplan(ecdr, Sol[0][j]);
            double f2=pct_semiplan(ecdr, Sol[0][j+1]);
            if(f1<=EPS && f2<=EPS)
            {
                Sol[1][++nrnou]=Sol[0][j+1];
                continue;
            }
            if(f1<=EPS && f2>0)
            {
                Punct=pct_intersectie(ecdr, ecur);
                Sol[1][++nrnou]=Punct;
                continue;
            }
            if(f1>0 && f2<=EPS)
            {
                Punct=pct_intersectie(ecdr, ecur);
                Sol[1][++nrnou]=Punct;
                Sol[1][++nrnou]=Sol[0][j+1];
            }
        }
        for(int j=1;j<=nrnou;j++)
            Sol[0][j]=Sol[1][j];
        nr=nrnou;
    }
}
void write()
{
    double Arie=0;
    Sol[0][++nr]=Sol[0][1];

    for(int i=1;i<nr;i++)
        Arie=Arie+(Sol[0][i].x * Sol[0][i+1].y - Sol[0][i].y * Sol[0][i+1].x);
    fout<<fixed<<setprecision(2)<<fabs(Arie/2);
}
int main()
{
    read();
    verif();
    solve();
    write();
    return 0;
}