Cod sursa(job #1182440)

Utilizator misinoonisim necula misino Data 6 mai 2014 14:20:40
Problema Camera Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include<fstream>
#include<algorithm>
#include<cmath>
#include<iomanip>

#define INF 100000
#define eps 0.000001
#define N 2010

using namespace std;

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

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

double a,b,c;

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

inline double aria(){
    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;
}

inline int afla_parte(double x,double y){
    int p = x * a + y * b + c;

    if(p < -eps)
        return -1;
    else
        if(p > eps)
        return 1;
    return 0;
}

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

int main()
{
    f >> n;

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

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

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


    for(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;

        for(j = 1 ; j <= m ; ++ j)
            parte[j] = afla_parte(sol[j].x , sol[j].y);

        nm = 0;

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

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

        for(j = 1 ; j <= nm ; ++ j)
            sol[j] = ns[j];

        m = nm;
    }
    -- m;
    for(i = 1 ; i <= m ; ++i)
        p[i] = sol[i];

    n = m;

    g << fixed << setprecision(3) << fabs(aria()) / 2 << '\n';

    return 0;
}