Cod sursa(job #2404357)

Utilizator Bodo171Bogdan Pop Bodo171 Data 12 aprilie 2019 16:43:16
Problema Camera Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
const int nmax=2005;
const int lim=100*1000+1;
const long double eps=0.000000001;
typedef long double ldouble;
struct punct
{
    ldouble x,y;
}ini[nmax],v[2*nmax],newv[2*nmax];
int nr,newnr,i,need,n,lat;
struct dreapta
{
    ldouble a,b,c;
    dreapta()
    {
    }
    dreapta(punct unu,punct doi)
    {
        this->a=unu.y-doi.y;
        this->b=doi.x-unu.x;
        this->c=-1LL*this->a*unu.x-1LL*this->b*unu.y;
    }
};
long double ev(dreapta d,punct P)
{
     return d.a*P.x+d.b*P.y+d.c;
}
int sgn(dreapta d,punct P)
{
    ldouble rt=d.a*P.x+d.b*P.y+d.c;
    if(rt<eps&&rt>-eps) return 0;
    if(rt>0) return 1;
    return -1;
}
punct ins(dreapta unu,dreapta doi)
{
    ldouble det1=(unu.a*doi.b-doi.a*unu.b),det2=(-unu.c*doi.b+doi.c*unu.b),det3=(-unu.a*doi.c+doi.a*unu.c);
    punct ret;
    ret.x=det2/det1;ret.y=det3/det1;
    return ret;
}
void taie(dreapta D)
{
    newnr=0;
    int start=1;
     for(i=1;i<=nr;i++)
    {
        if(sgn(D,v[i])==need)
        {
            if(sgn(D,v[i-1])==-need)
            {
                dreapta aux(v[i],v[i-1]);
                newv[++newnr]=ins(aux,D);
            }
            newv[++newnr]=v[i];
            if(sgn(D,v[i+1])==-need)
            {
                dreapta aux(v[i],v[i+1]);
                newv[++newnr]=ins(aux,D);
            }
        }
        if(sgn(D,v[i])==0)
        {
            newv[++newnr]=v[i];
        }
    }
    nr=newnr;
    for(i=1; i<=newnr; i++)
    {
        v[i]=newv[i];
    }
    v[0]=v[nr];
    v[nr+1]=v[1];
}
long double calc_arie(punct vv[],int lim)
{
    long double arie=0;
    for(i=1;i<=lim;i++)
    {
        arie+=(vv[i].x*vv[i+1].y-vv[i].y*vv[i+1].x);
    }
    return arie;
}
int main()
{
    ifstream f("camera.in");
    ofstream g("camera.out");
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>ini[i].x>>ini[i].y;
    }
    ini[n+1]=ini[1];
    ini[0]=ini[n];
    long double A=calc_arie(ini,n);
    if(A<0)
    {
        reverse(ini+1,ini+n+1);
    }
    ini[n+1]=ini[1];
    ini[0]=ini[n];
    nr=4;
    v[1]={-lim,-lim};v[2]={lim,-lim};v[3]={lim,lim};v[4]={-lim,lim};
    v[0]=v[4];v[5]=v[1];
    need=1;
    for(lat=1;lat<=n;lat++)
    {
        taie(dreapta(ini[lat],ini[lat+1]));
    }
    A=calc_arie(v,nr);
    if(A<0) A*=-1;
    A/=2;
    g<<fixed<<setprecision(6)<<A;
    return 0;
}