Cod sursa(job #979019)

Utilizator mitrutstrutMitrea Andrei Ionut mitrutstrut Data 31 iulie 2013 10:19:30
Problema Camera Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.09 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)));
 
}