Cod sursa(job #1200667)

Utilizator misinoonisim necula misino Data 23 iunie 2014 12:31:43
Problema Camera Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.26 kb
#include<fstream>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<cmath>

#define N 2010
#define eps 1e-6
#define INF 100001

using namespace std;

ifstream f("camera.in");
ofstream g("camera.out");

int i,n,m,mn,p1,p2,j;

double a,b,c;

struct punct{double x,y;}p[N],sol[N],soln[N];

inline double aria(punct p[],int n){
    double s = 0;

    p[n + 1] = p[1];

    for(i = 1 ; i <= n ; ++ i)
        s += p[i].x * p[i + 1].y - p[i].y * p[i + 1].x;

    return s / 2;
}

inline punct punct_intersectie(punct p1 , punct p2){
    double a1 , b1 , c1;
    a1 = p2.y - p1.y;
    b1 = p1.x - p2.x;
    c1 = p2.x * p1.y - p2.y * p1.x;

    double det = a * b1 - a1 * b;

    return (punct){(b * c1 - b1 * c) / det , (a1 * c - c1 * a) /det };
}

inline bool parte(punct p){
    double ec = p.x * a + p.y * b + c;

    if(ec <= eps)
        return 1;

    return 0;
}

int main()
{
    f >> n ;

    for(i = 1 ; i <= n ; ++ i)
    {
        f >> p[i].x >> p[i].y;
    }

    p[n + 1] = p[1];

    ///Sens trigonometric
    if(aria(p , n) < -eps)
        reverse(p + 1 , p + n + 1);
    p[n + 1] = p[1];

    m = 4;

    sol[1]=(punct){-INF,-INF};
    sol[2]=(punct){INF,-INF};
    sol[3]=(punct){INF,INF};
    sol[4]=(punct){-INF,INF};

    for(int i = 1 ; i <= n ; ++ i)
    {
        a = p[i + 1].y - p[i].y;
        b = p[i].x - p[i + 1].x;
        c = p[i + 1].x * p[i].y - p[i].x * p[i + 1].y;

        sol[m + 1] = sol[1];

        mn = 0;

        for(j = 1 ; j <= m ; ++ j)
        {
            p1 = parte(sol[j]);
            p2 = parte(sol[j + 1]);

            if(!p1 && p2)
            {
                soln[++ mn] = punct_intersectie(sol[j],sol[j + 1]);
                soln[++ mn] = sol[j + 1];
            }
            else
                if(p1 && !p2)
                {
                    soln[++ mn] = punct_intersectie(sol[j] , sol[j + 1]);
                }
                else
                    if(p1 && p2)
                    {
                        soln[++ mn] = sol[j + 1];
                    }
        }

        memcpy(sol,soln,sizeof(soln));

        m = mn;
    }

    g << fixed << setprecision(2) << fabs(aria(sol,m)) << '\n';

    return 0;
}