Cod sursa(job #1903063)

Utilizator patrutoiuandreipatrutoiu andrei patrutoiuandrei Data 4 martie 2017 22:52:42
Problema Camera Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <fstream>
#include <iomanip>

#define Ndim 2002
#define xmax  100000
using namespace std;
ifstream fin("camera.in");
ofstream fout("camera.out");
struct point
{
    long double x,y;
}P[Ndim],SOL[2][Ndim];
long double abs(long double x)
{
    return max(x,-x);
}
long double det(point p1,point p2,point p3)
{
    return p1.x*(p2.y-p3.y) + p2.x*(p3.y-p1.y) + p3.x*(p1.y-p2.y);
}
point intseg(point p1,point p2,point p3,point p4)
{
    long double a1 = p1.y-p2.y, b1 = p2.x-p1.x, c1 = p1.x*p2.y - p1.y*p2.x;
    long double a2 = p3.y-p4.y, b2 = p4.x-p3.x, c2 = p3.x*p4.y - p3.y*p4.x;
    point p;
    long double x = (b1*c2-b2*c1)/(a1*b2-b1*a2);
    long double y = (c2*a1-c1*a2)/(b1*a2-b2*a1);
    p.x = x;p.y = y;
    return p;

}
long double solve(int f,int l,int t)
{
    int i,j,c=1,newsoldim,soldim;
    long double d1,d2;
    point a,b,p1,p2;
    SOL[1][1].x = -xmax; SOL[1][1].y = -xmax;
    SOL[1][2].x = -xmax;SOL[1][2].y = xmax;
    SOL[1][3].x = xmax;SOL[1][3].y = xmax;
    SOL[1][4].x = xmax;SOL[1][4].y = -xmax;
    SOL[1][5] = SOL[1][1];
    soldim = 5;
    for(i=f;i!=l;i+=(t*1))
    {
        newsoldim = 0;
        c = 1-c;
        for(j=1;j<soldim;j++)
        {
            a = SOL[1-c][j];
            b = SOL[1-c][j+1];
            p1 = P[i];
            p2 = P[i+t*1];
            d1 = det(p1,p2,a);
            d2 = det(p1,p2,b);
            if(d1 >= 0 && d2 >= 0)
            {
                SOL[c][++newsoldim] = b;
            }
            else if(d1 < 0 && d2 >= 0)
            {
                if(d2 == 0)
                    SOL[c][++newsoldim] = b;
                else
                {
                    SOL[c][++newsoldim] = intseg(a,b,p1,p2);
                    SOL[c][++newsoldim] = b;
                }
            }
            else if(d1 > 0)
            {
                SOL[c][++newsoldim] = intseg(a,b,p1,p2);
            }
        }
        SOL[c][++newsoldim] = SOL[c][1];
        soldim = newsoldim;
    }
    long double sol = 0;
    for(i=3;i<soldim;i++)
    {
        sol += abs(det(SOL[c][1],SOL[c][i-1],SOL[c][i]));
    }
    return sol/2.0;
}
int main()
{
    int n,i;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>P[i].x>>P[i].y;
    }
    P[++n] = P[1];
    fout<< setprecision(2)<<fixed<<max(solve(1,n,1),solve(n,1,-1));
    return 0;
}