Cod sursa(job #2044860)

Utilizator georgerapeanuRapeanu George georgerapeanu Data 21 octombrie 2017 15:24:03
Problema Camera Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.74 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
FILE *f=fopen("camera.in","r");
FILE *g=fopen("camera.out","w");
struct punct
{
    double x,y;
    punct()
    {
        ;
    }
    punct(double X,double Y)
    {
        x=X;
        y=Y;
    }
    bool operator < (const punct &other)const
    {
        if(x!=other.x)return x<other.x;
        return y<other.y;
    }
};
struct dreapta
{
    double a,b,c;
    dreapta()
    {
        ;
    }
    dreapta(punct P1,punct P2)
    {
        a=P2.y-P1.y;
        b=P1.x-P2.x;
        c=P2.x*P1.y-P1.x*P2.y;
    }
    punct n(dreapta &other)
    {
        punct rez;
        rez.y=(c*other.a-other.c*a)/(other.b*a-b*other.a);
        if(a)rez.x=(-c-b*rez.y)/a;
        else rez.x=(-other.c-other.b*rez.y)/other.a;
        return rez;
    }
};
struct semiplan
{
    int sign;
    dreapta d;
    semiplan()
    {
        ;
    }
    semiplan(dreapta D,int sens)
    {
        sign=sens;
        d=D;
    }
};
double det(punct a,punct b,punct c)
{
    return a.x*b.y-a.x*c.y+b.x*c.y-b.x*a.y+c.x*a.y-c.x*b.y;
}
int N,M=4;
punct V[2005];
punct P[6005];
punct tmp[6005];
semiplan S[2005];
int main()
{
    P[1]={1e5,1e5};
    P[2]={-1e5,1e5};
    P[3]={-1e5,-1e5};
    P[4]={1e5,-1e5};
    fscanf(f,"%d",&N);
    for(int i=1;i<=N;i++)
    {
        fscanf(f,"%lf %lf",&V[i].x,&V[i].y);
        P[1].x=min(P[1].x,V[i].x);P[1].y=min(P[1].y,V[i].y);
        P[2].x=max(P[2].x,V[i].x);P[2].y=min(P[2].y,V[i].y);
        P[3].x=max(P[3].x,V[i].x);P[3].y=max(P[3].y,V[i].y);
        P[4].x=min(P[4].x,V[i].x);P[4].y=max(P[4].y,V[i].y);
    }
    double area=0;for(int i=1;i<=N;i++)area+=det({0,0},V[i],V[i%N+1]);
    if(area<0)reverse(V+1,V+1+N);
    for(int i=1;i<=N;i++)if(i)S[i-1]=semiplan(dreapta(V[i-1],V[i]),-1);S[N]=semiplan(dreapta(V[N],V[1]),-1);
    for(int i=1;i<=N;i++)
    {
        int ind=0;
        for(int j=1;j<=M;j++)
        {
            dreapta D(P[j],P[(j-2+M)%M+1]);
            double a,b;
            b=S[i].d.a*P[j].x+S[i].d.b*P[j].y+S[i].d.c;
            a=S[i].d.a*P[(j-2+M)%M+1].x+S[i].d.b*P[(j-2+M)%M+1].y+S[i].d.c;
            if(b*S[i].sign>0)
            {
                if(a*S[i].sign<=0)
                {
                    tmp[++ind]=D.n(S[i].d);
                }
                tmp[++ind]=P[j];
            }
            else
            {
                if(a*S[i].sign>0)
                {
                    tmp[++ind]=D.n(S[i].d);
                }
            }
        }
        M=ind;
        memcpy(P,tmp,sizeof(tmp));
    }
    area=0;for(int i=1;i<=M;i++)area+=det({0,0},P[i],P[i%M+1]);
    fprintf(g,"%.4f",area/2);
    fclose(f);
    fclose(g);
    return 0;
}