Cod sursa(job #179901)

Utilizator sealTudose Vlad seal Data 16 aprilie 2008 13:58:25
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include<stdio.h>
#define Nm 2048
#define Inf 100000
#define eps 1e-6
#define abs(a) ((a)<0?-(a):(a))
int X0[Nm],Y0[Nm],N[2],c,p,n;
double X[2][Nm],Y[2][Nm],ans;

void read()
{
    int i;

    freopen("camera.in","r",stdin);
    scanf("%d",&n);
    for(i=0;i<n;++i)
        scanf("%d%d",X0+i,Y0+i);
}

inline double cross(double x0, double y0, double x1, double y1, double x2, double y2)
{
    return (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);
}

void swap(int &a, int &b) { a=a^b; b=a^b; a=a^b; }

inline void insert(double x, double y)
{
    if(!N[c] || abs(X[c][N[c]-1]-x)>=eps || abs(Y[c][N[c]-1]-y)>=eps)
        X[c][N[c]]=x, Y[c][N[c]++]=y;
}

inline void intersect(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4, double &x, double &y)
{
    double a1,b1,c1,a2,b2,c2;

    a1=y1-y2; a2=y3-y4;
    b1=x2-x1; b2=x4-x3;
    c1=x1*y2-x2*y1; c2=x3*y4-x4*y3;

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

void solve()
{
    int i,j;
    double area=0,c1,c2,x,y;

    for(i=1;i<n-1;++i)
        area+=cross(X0[0],Y0[0],X0[i],Y0[i],X0[i+1],Y0[i+1]);
    if(area<0)
        for(i=0;i<n/2;++i)
        {
            swap(X0[i],X0[n-i-1]);
            swap(Y0[i],Y0[n-i-1]);
        }

    N[0]=4;
    X[0][0]=X[0][4]=-Inf; Y[0][0]=Y[0][4]=-Inf;
    X[0][1]=Inf; Y[0][1]=-Inf;
    X[0][2]=Inf; Y[0][2]=Inf;
    X[0][3]=-Inf; Y[0][3]=Inf;

    X0[n]=X0[0]; Y0[n]=Y0[0];
    for(c=1,p=0,i=0;i<n;++i,c^=1,p^=1)
    {
        for(N[c]=j=0;j<N[p];++j)
        {
            c1=j?c2:cross(X0[i],Y0[i],X0[i+1],Y0[i+1],X[p][j],Y[p][j]);
            c2=cross(X0[i],Y0[i],X0[i+1],Y0[i+1],X[p][j+1],Y[p][j+1]);
            if(c1<=-eps && c2<=-eps) continue;
            if(c1>-eps && c2>-eps)
            {
                insert(X[p][j+1],Y[p][j+1]);
                continue;
            }
            intersect(X0[i],Y0[i],X0[i+1],Y0[i+1],X[p][j],Y[p][j],X[p][j+1],Y[p][j+1],x,y);
            insert(x,y);
            if(c2>-eps) insert(X[p][j+1],Y[p][j+1]);
        }
        if(abs(X[c][0]-X[c][N[c]-1])<eps && abs(Y[c][0]-Y[c][N[c]-1])<eps)
            --N[c];
        X[c][N[c]]=X[c][0]; Y[c][N[c]]=Y[c][0];
    }

    for(i=1;i<N[p]-1;++i)
        ans+=cross(X[p][0],Y[p][0],X[p][i],Y[p][i],X[p][i+1],Y[p][i+1]);
    ans/=2;
}

void write()
{
    freopen("camera.out","w",stdout);
    printf("%.2lf\n",ans);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}