Cod sursa(job #965613)

Utilizator ericptsStavarache Petru Eric ericpts Data 24 iunie 2013 11:54:05
Problema Camera Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.64 kb
#include <cstdio>
#include <utility>
#include <algorithm>
#include <cstring>

using namespace std;
#define same(a,b) (abs(a-b) <= EPS)

struct point{
    double x,y;
    point():
        x(0),y(0)
    {}
    point(double x,double y):
        x(x),y(y)
    {}
};
typedef point line;
const int INF = (1<<30)-1;
const int MAX_N = 2010;
const double EPS = 1e-6;
const double EPS2 = EPS*EPS;
const point O;


point v[MAX_N];
point sol[MAX_N];
point aux[MAX_N];
int n,m,p;

const inline int sign(const double &X)
{
    if(X < -EPS)
        return -1;

    if(X < EPS)
        return 0;

    return 1;
}

const inline line liniarize(const point &A,const point &B)
{
    const double m = (A.y-B.y)/(A.x-B.x + EPS2);
    const double b = A.y - m * A.x;

    return line(m,b);
}

const inline point intersect(const point &A,const point &B,const point &X,const point &Y)
{
    line AB = liniarize(A,B), XY = liniarize(X,Y);

    const double x = (AB.y - XY.y) / (XY.x - AB.x + EPS2);
    const double y = AB.x * x + AB.y;

    return point(x,y);
}

const inline double cross(const point &a,const point &b,const point &c)
{
    const double x1 = a.x - b.x,
                 y1 = a.y - b.y,
                 x2 = c.x - a.x,
                 y2 = c.y - a.y;

    return x1*y2 - x2*y1;
}

inline double area(point * P, int argc)
{
    double ret = 0;

    for(int i = 1 ; i <= argc ; ++ i)
        ret += cross(O,P[i],P[i % argc+1]);

    ret /= 2;

    return ret;
}


int main()
{
    freopen("camera.in", "r", stdin);
    freopen("camera.out", "w", stdout);

    scanf("%d",&n);

    for(int i = 1 ; i <= n ; ++ i)
        scanf("%lf%lf",&v[i].x,&v[i].y);

    v[n+1] = v[1];

    sol[++m] = point(INF,INF);
    sol[++m] = point(INF,-INF);
    sol[++m] = point(-INF,-INF);
    sol[++m] = point(-INF,INF);

    int i,j;

    int overall = sign(area(v,n));
    int now,next;

    for(i = 1 ; i <= n ; ++ i){
        sol[m+1] = sol[1];
        p = 0;
        for(j = 1 ; j <= m ; ++ j){

            now = sign(cross(v[i],v[i+1],sol[j]));
            next = sign(cross(v[i],v[i+1],sol[j+1]));

            if(now == overall && next == overall)
                aux[++p] = sol[j+1];
            else if(now == overall && next != overall)
                aux[++p] = intersect(v[i],v[i+1],sol[j],sol[j+1]);
            else if(now != overall && next == overall){
                aux[++p] = intersect(v[i],v[i+1],sol[j],sol[j+1]);
                aux[++p] = sol[j+1];
            }

        }
        memcpy(sol,aux,(p+1)*sizeof(point));
        m = p;
    }
    printf("%.2lf",abs(area(sol,m)));

}