Cod sursa(job #1001420)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 24 septembrie 2013 22:11:34
Problema Camera Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream f("camera.in");
ofstream g("camera.out");

#define x first
#define y second
#define mp make_pair
#define db long double
#define pdd pair<double,double>
#define eps 0.0000001
#include <cmath>
#define LE 66666
#include <iomanip>

struct trei
{
    db fi,se,th;
};

void rott(pdd &F,db alf)
{
    F=mp( F.x*cos(alf)-F.y*sin(alf), F.x*sin(alf)+F.y*cos(alf) );
}

db cross(pdd i1,pdd i2,pdd i3)
{
    i2=mp(i2.x-i1.x,i2.y-i1.y);
    i3=mp(i3.x-i1.x,i3.y-i1.y);
    db val=(i2.y*i3.x-i2.x*i3.y);
    return val;
}

trei mk3(db i1,db i2,db i3)
{
    trei res;
    res.fi=i1,res.se=i2,res.th=i3;
    return res;
}

trei get_ecc(pdd i1,pdd i2)
{
    db A=i1.y-i2.y;
    db B=i2.x-i1.x;
    db C=i1.x*i2.y-i2.x*i1.y;
    return mk3(A,B,C);
}

pdd intr(trei i1,trei i2)
{
    db Ys=(i2.th*i1.fi-i1.th*i2.fi)/(i2.fi*i1.se-i2.se*i1.fi);
    db Xs=(-i1.th-i1.se*Ys)/(i1.fi);
    return mp(Xs,Ys);
}

int semn(db val)
{
    if (val>=-eps&&val<=eps) return 0;
    if (val>0) return 1;
    return -1;
}

pdd X[LE],pol[LE],pol2[LE];
int i,j,k,k2,n;

int main()
{
    f>>n;
    for(i=1; i<=n; ++i)
    {
        f>>X[i].x>>X[i].y;
        rott(X[i],0.1);
    }

    for(i=1; i<=n; ++i) pol[i]=X[i];
    X[n+1]=X[1];
    X[0]=X[n];

    k2=0,k=n;
    // for(i=1; i<=n; ++i) cout<<pol[i].x<<" "<<pol[i].y<<'\n';

    // cout<<semn(cross(X[1],X[2],X[0]))<<'\n';
    // cout<<semn(cross(X[1],X[2],X[3]));


    for(i=1; i<=n; ++i)
    {
        int _sign=1;

        pol[k+1]=pol[1];
        pol[0]=pol[k];

        for(j=1; j<=k; ++j)
        {
            int semn1=semn(cross(X[i],X[i+1],pol[j]));
            int semn2=semn(cross(X[i],X[i+1],pol[j+1]));

            if (semn1!=semn2&&semn1!=0&&semn2!=0)
                pol2[++k2]=intr(get_ecc(pol[j],pol[j+1]),get_ecc(X[i],X[i+1]));

            if (semn2==_sign||semn2==0) pol2[++k2]=pol[j+1];
        }

        k=k2,k2=0;
        for(j=1; j<=k; ++j) pol[j]=pol2[j];
    }

    pol[k+1]=pol[1];
    db arie=0;

    for(i=1; i<=k; ++i)
        arie+=cross(mp(0,0),pol[i],pol[i+1]);

    g<<fixed;
    g<<setprecision(6);
    g<<arie/2.0;


    f.close();
    g.close();
    return 0;
}