Cod sursa(job #2404150)

Utilizator Bodo171Bogdan Pop Bodo171 Data 12 aprilie 2019 12:46:25
Problema Camera Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
const int nmax=2005;
const int lim=100*1000+1;
const double eps=0.0000001;
struct punct
{
    double x,y;
}ini[nmax],v[2*nmax],newv[2*nmax];
int nr,newnr,i,need,n,lat;
struct dreapta
{
    double a,b,c;
    dreapta()
    {
    }
    dreapta(punct unu,punct doi)
    {
        this->a=doi.y-unu.y;
        this->b=unu.x-doi.x;
        this->c=-1LL*this->a*unu.x-1LL*this->b*unu.y;
    }
};
int sgn(dreapta d,punct P)
{
    double 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)
{
    //nu cred ca acopere 2 drepte cu x constant
    punct ret;
    if(doi.b<eps&&doi.b>-eps) swap(unu,doi);
    if(doi.b>eps||doi.b<eps)
    {
        unu.a-=doi.a*unu.b/doi.b;
        unu.b=0;
        unu.c-=doi.c*unu.b/doi.b;
        ret.x=-unu.c/unu.a;
        ret.y=(-doi.c-ret.x*doi.a)/doi.b;
    }
    cout<<sgn(unu,ret)<<' '<<sgn(doi,ret)<<' '<<unu.b<<' '<<doi.b<<"pp\n";
    return ret;//daca sunt paralele sau coincid,aia e
}
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;
}