Cod sursa(job #1182802)

Utilizator misinoonisim necula misino Data 7 mai 2014 18:25:49
Problema Camera Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#include<fstream>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<cmath>

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

using namespace std;

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

int n,i,ns,m,j,parte[N];

double a,b,c;

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

inline void coordonate(double &a, double &b, double &c, punct p1, punct p2){
    a = p2.y - p1.y;
    b = p1.x - p2.x;
    c = p2.x * p1.y - p1.x * p2.y;
}

inline int afla_parte(punct p){
    int ec = p.x * a + p.y * b + c;

    if(ec < -eps)
    return -1;

    if(ec > eps)
    return 1;

    return 0;
}

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

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

    return a;
}

inline punct punct_intersectie(punct p1 , punct p2){
    double a1 , b1 , c1;

    coordonate(a1 , b1 , c1 , p1 , p2);

    double det = a * b1 - a1 * b;

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


int main()
{
    f >> n;

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

    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};

    if(aria(p , n) > eps)
        reverse(p + 1 , p + n + 1);

    for(i = 1 ; i <= n ; ++ i)
    {
        coordonate(a , b , c , p[i] , p[i + 1]);

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

        for(j = 1 ; j <= m + 1; ++ j)
            parte[j] = afla_parte(sol[j]);

        ns = 0;

        for(j = 1 ; j <= m ; ++ j)
        {
            if(parte[j] >= 0 && parte[j + 1] >= 0)
                soln [++ ns] = sol[j];
            else
                if(parte[j] >= 0)
                soln[ ++ ns] = sol[j] , soln[++ ns] = punct_intersectie(sol[j] , sol[j + 1]);
            else
                if(parte[j + 1] >= 0)
                soln[++ ns] = punct_intersectie(sol[j] , sol[j + 1]);
        }

        m = 1;
        sol[1] = soln[1];

        for(j = 2 ; j <= ns ; ++ j)
            if(soln[j].x != sol[m].x || soln[j].y != sol[m].y)
                sol[++ m] = soln[j];

     //   if(sol[m].x == sol[1].x && sol[m].y == sol[1].y)
       //     -- m;
    }

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

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

    return 0;
}