Cod sursa(job #476268)

Utilizator freak93Adrian Budau freak93 Data 10 august 2010 14:56:41
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.68 kb
#include<fstream>
#include<algorithm>
#define punct pair<double,double>
#define x first
#define y second

using namespace std;

const char iname[]="camera.in";
const char oname[]="camera.out";
const int maxn=4005;
const double inf=1e6;

ifstream f(iname);
ofstream g(oname);

punct a[maxn],kernel[maxn],kernelaux[maxn];

double area,minx,miny,maxx,maxy,eps=1e-6;

int i,j,n,sgn,k;

int cmp(double a,double b)
{
    if(a+eps<b)
        return -1;
    if(b+eps<a)
        return 1;
    return 0;
}

int semn(punct a,punct b,punct c)
{
    double x=a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
    return cmp(x,0);
}

punct intersect(punct a,punct b,punct c,punct d)
{
    double a1,b1,a2,b2;
    double x,y;
    if(a.x==b.x)
        a1=inf;
    else
        a1=(a.y-b.y)/(a.x-b.x);
    if(c.x==d.x)
        a2=inf;
    else
        a2=(c.y-d.y)/(c.x-d.x);
    b1=a.y-a1*a.x;
    b2=c.y-a2*c.x;
    if(cmp(a1,inf)==0)
    {
        x=a.x;
        y=a2*x+b2;
    }
    else
        if(cmp(a2,inf)==0)
        {
            x=c.x;
            y=a1*x+b1;
        }
        else
        {
            x=(b2-b1)/(a1-a2);
            y=a1*x+b1;
        }
    return punct(x,y);
}

int main()
{
    f>>n;
    for(i=0;i<n;++i)
        f>>a[i].x>>a[i].y,minx=min(minx,a[i].x),miny=min(miny,a[i].y),maxx=max(maxx,a[i].x),maxy=max(maxy,a[i].y);
    a[n]=a[0];
    for(i=0;i<n;++i)
        area+=a[i].x*a[i+1].y-a[i+1].x*a[i].y;
    if(area>0)
        sgn=1;
    else
        sgn=-1;

    kernel[0]=punct(minx,miny);
    kernel[1]=punct(maxx,miny);
    kernel[2]=punct(maxx,maxy);
    kernel[3]=punct(minx,maxy);
    k=4;
    for(i=0;i<n;++i)
    {
        int start=0,next=1;
        int newk=0;
        if(k>2)
        do
        {
            int s1=semn(a[i],a[i+1],kernel[start]);
            int s2=semn(a[i],a[i+1],kernel[next]);
            if(s1!=-sgn&&s2!=-sgn)
                kernelaux[newk++]=kernel[next];
            else
                if(s1!=-sgn)
                    kernelaux[newk++]=intersect(a[i],a[i+1],kernel[next],kernel[start]);
                else
                    if(s2!=-sgn)
                        kernelaux[newk++]=intersect(a[i],a[i+1],kernel[next],kernel[start]),kernelaux[newk++]=kernel[next];
            ++start;
            if(start==k)
                start=0;
            ++next;
            if(next==k)
                next=0;
        }
        while(start!=0);
        for(j=0,k=newk;j<k;++j)
            kernel[j]=kernelaux[j];
    }
    if(k<3)
    {
        g<<"0.00\n";
        return 0;
    }
    area=0;
    kernel[k]=kernel[0];
    for(i=0;i<k;++i)
        area+=kernel[i].x*kernel[i+1].y-kernel[i+1].x*kernel[i].y;
    area/=2.0;
    g.setf(ios::fixed,ios::floatfield);
    g.precision(2);
    g<<area<<"\n";
}