Cod sursa(job #1669184)

Utilizator GinguIonutGinguIonut GinguIonut Data 30 martie 2016 14:35:58
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.86 kb
#include <fstream>
#include <iomanip>
#include<cmath>
#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 EPS 1e-6
#define nMax 2009
#define mkp make_pair
#define INF 100001


using namespace std;
ifstream fin("camera.in");
ofstream fout("camera.out");
int n, nr, nrnou;
pdd Pct[nMax], Sol[2][nMax],Punct;
pddd ecdr, ecur;
double Arie;
void read()
{
    double a, b;
    fin>>n;

    for(int i=1;i<=n;i++)
    {
        fin>>a>>b;
        Pct[i]=mkp(a, b);
    }
    Pct[n+1]=Pct[1];
}
void verif()
{
    double Arie=0;

    for(int i=1;i<=n;i++)
        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];
    }

}
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-a.x*b.y;

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

pdd pct_intersectie(const pddd& ecdr, const pddd& ecur)
{
    pdd sol;
    sol.x=(ecur.B * ecdr.C - ecdr.B * ecur.C)/(ecdr.B * ecur.A - ecur.B* ecdr.A);
    sol.y=(ecdr.C*ecur.A-ecdr.A*ecur.C)/(ecdr.A*ecur.B-ecdr.B*ecur.A);  // am inlocuit y facand aceeasi operatie ca pentru x

    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++)
        {
            double f1=pct_semiplan(ecdr, Sol[0][j]);
            double f2=pct_semiplan(ecdr, Sol[0][j+1]);
            ecur=ec_dreapta(Sol[0][j], 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];
                continue;
            }
        }
        for(int j=1;j<=nrnou;j++)
            Sol[0][j]=Sol[1][j];
        nr=nrnou;
    }

    Sol[0][++nr]=Sol[0][1];

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