Cod sursa(job #2164149)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 12 martie 2018 21:44:39
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.94 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
#define maxN 10005
#define eps 0.000001
#define inf 100005
using namespace std;
ifstream fin("camera.in");
ofstream fout("camera.out");
int m,j ;
struct segm
{
    double x1;
    double y1;
    double x2;
    double y2;
    segm(){}
    segm(pair<double,double> a,pair<double,double> b)
    {
        x1=a.first;
        y1=a.second;
        x2=b.first;
        y2=b.second;
    }

};

inline double det(double x1,double y1,double x2,double y2,double x3,double y3)
{
    return (x2-x1)*(y3-y1)-(x3-x1)*(y2-y1);
}

inline bool egal(double a,double b)
{
    double dif=a-b;
    if(dif>=-eps && dif<=eps) return 1;
    return 0;
}
int n;
pair<double,double> v[maxN],w[maxN];
double sol;
inline int nxt(int i,int n)
{
    if(i==n) return 1;
    return i+1;
}
int t,k;
pair<double,double> intersect(segm a,segm b)
{
    double a1=a.y2-a.y1;
    double b1=a.x1-a.x2;
    double c1=a.y1*(a.x2-a.x1)-a.x1*(a.y2-a.y1);

    double a2=b.y2-b.y1;
    double b2=b.x1-b.x2;
    double c2=b.y1*(b.x2-b.x1)-b.x1*(b.y2-b.y1);

    double x = (double)(b1*c2 - b2*c1) * 1.0 / (b2*a1 - b1*a2);
    double y = (double)(a1*c2 - a2*c1) * 1.0 / (a2*b1 - a1*b2);

    return make_pair(x,y);
}
pair<double,double> p[maxN];
inline int semn(int i,int j,int k)
{
    double t=det(v[i].first,v[i].second,v[j].first,v[j].second,p[k].first,p[k].second);
    if(egal(t,0)) return 0;
    if(t<0) return -1;
    return 1;
}

int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
       fin>>v[i].first>>v[i].second;

    for(int i=1;i<=n;i++)
        sol+=det(0,0,v[i].first,v[i].second,v[nxt(i,n)].first,v[nxt(i,n)].second);


   // double ax;
    if(sol<0)
    {
        for(int i=2,j=n;i<j;i++,j--)
            swap(v[i],v[j]);
    }

    p[1]={-inf,-inf};
    p[2]={inf,-inf};
    p[3]={inf,inf};
    p[4]={-inf,inf};

    m=4;
    int nexti;
    for(int i=1;i<=n;i++)
    {
        nexti=nxt(i,n);
        j=1;
        for(j=1;j<=m;j++)
        {
            if(det(v[i].first,v[i].second,v[nexti].first,v[nexti].second,p[j].first,p[j].second)>0)
            {
                break;
            }
        }

        if(j==m+1)
        {
            fout<<0<<'\n';
            return 0;
        }

        t=0;
        k=j;
        do
        {
            int nk=nxt(k,m);
            if(semn(i,nexti,k)>0)
            {
                if(semn(i,nexti,nk)>0)
                {
                    w[++t]=p[nk];
                }
                    else
                if(semn(i,nexti,nk)==0)
                {
                    w[++t]=p[nk];
                }
                    else
                {
                    segm a(v[i],v[nexti]);
                    segm b(p[k],p[nk]);
                    pair<double,double> r=intersect(a,b);
                    w[++t]=r;
                }
            }
            if(semn(i,nexti,k)==0)
            {
                if(semn(i,nexti,nk)>0)
                    w[++t]=p[nk];
                    else
                if(semn(i,nexti,nk)==0)
                    w[++t]=p[nk];
            }
            if(semn(i,nexti,k)<0)
            {
                if(semn(i,nexti,nk)>0)
                {
                    segm a(v[i],v[nexti]);
                    segm b(p[k],p[nk]);
                    pair<double,double> r=intersect(a,b);
                    w[++t]=r;
                    w[++t]=p[nk];
                }
                    else
                {
                    if(semn(i,nexti,nk)==0) w[++t]=p[nk];
                }
            }
            k=nk;
        }while(k!=j);

        m=t;
        for(int j=1;j<=t;j++)
            p[j]=w[j];
    }
    sol=0;
    for(int i=1;i<=m;i++)
        sol+=det(0,0,p[i].first,p[i].second,p[nxt(i,m)].first,p[nxt(i,m)].second);
    if(sol<0) sol=-sol;

    fout<<setprecision(2)<<fixed<<sol/2.0<<'\n';
    return 0;

}