Cod sursa(job #967795)

Utilizator sleepaholicNeculaescu Theodor sleepaholic Data 28 iunie 2013 14:58:28
Problema Camera Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.05 kb
#include <cstdio>
#include <utility>
#include <algorithm>
#include <cstring>

using namespace std;

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<<25)-1;
const int MAX_N = 2010;
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 < 0)
        return -1;
    else return 1;
}

void coef(point A, point B, double &a, double &b, double &c) {
    a = B.y - A.y;
    b = A.x - B.x;
    c = B.x * A.y - A.x * B.y;
}

point intersection(point p1, point p2, point p3, point p4) {
    double a1, a2, b1, b2, c1, c2;
    coef (p1, p2, a1, b1, c1);
    coef (p3, p4, a2, b2, c2);

    point a;
    a.x = (c2 * b1 - c1 * b2) / (a1 * b2 - a2 * b1);
    a.y = (a1 * c2 - a2 * c1) / (a2 * b1 - a1 * b2);

    return a;

}

const inline point intersect(const point &A,const point &B,const point &X,const point &Y)
{
    double x1,x2,x3,x4,y1,y2,y3,y4;
    x1 = A.x,y1 = A.y;
    x2 = B.x,y2 = B.y;
    x3 = X.x,y3 = X.y;
    x4 = Y.x,y4 = Y.y;
    const double div = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4);
    point ret;
    ret.x = ( (x1*y2-y1*x2)*(x3-x4) - (x1-x2)*(x3*y4-y3*x4) )/div;
    ret.y = ( (x1*y2-y1*x2)*(y3-y4) - (y1-y2)*(x3*y4-y3*x4) )/div;

    return ret;
}

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

double solve(int overall)
{

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

    int i,j;

    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+30)*sizeof(point));
        m = p;
    }

    double A = area(sol,m);

    if( A < 0 )
        A = -A;

    return A;
}

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


    printf("%.2f",max(solve(1),solve(-1)));

}