Cod sursa(job #346634)

Utilizator GavrilaVladGavrila Vlad GavrilaVlad Data 8 septembrie 2009 19:36:49
Problema Camera Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define maxn 4100
#define inf 100001
#define eps 0.000001
struct punct
{
    double x; double y;
};

long n, i, j, k, w, semn, s1, s2;
double sol1, sol2;
punct p[maxn], v[maxn], cr[maxn];

long det(punct a, punct b, punct c)
{
    double aria = a.x*b.y + b.x*c.y + c.x*a.y - a.x*c.y - b.x*a.y - c.x*b.y;
  //  if(aria<eps && aria>-eps) return 0;
    if(aria<-eps) return -1;
    return 1;
}

punct interx(punct a, punct b, punct c, punct d)
{
    double a1, a2, b1, b2, c1, c2;
    punct rez;
    a1=(a.y-b.y);
    b1=(b.x-a.x);
    c1=-(a.x*b.y-b.x*a.y);
    a2=(c.y-d.y);
    b2=(d.x-c.x);
    c2=-(c.x*d.y-d.x*c.y);
    rez.x=(c1*b2-b1*c2)/(a1*b2-b1*a2);
    rez.y=(a1*c2-c1*a2)/(a1*b2-b1*a2);
    return rez;
}

double calc()
{
    double aria;
    k=4;
    v[1].x=-inf; v[1].y=-inf;  
    v[2].x=-inf; v[2].y=inf;
    v[3].x=inf; v[3].y=inf;
    v[4].x=inf; v[4].y=-inf;
    v[5]=v[1];
    for(i=1; i<=n; i++)
    {
        w=0;
        for(j=1; j<=k; j++)
        {
      /*      if(det(v[j], p[i], p[i+1])==0)
            {
            //    printf("*");
                cr[++w]=v[j];
            }*/
            else
            if(det(v[j], p[i], p[i+1])==semn)
            {
                cr[++w]=v[j];
                if(det(v[j+1], p[i], p[i+1])==-semn)
                {
                    cr[++w]=interx(v[j], v[j+1], p[i], p[i+1]);
                }
            }
            else
            if(det(v[j+1], p[i], p[i+1])==semn)
            {
                cr[++w]=interx(v[j], v[j+1], p[i], p[i+1]);
            }
        }
        if(w==0) return 0;
        k=w;
        for(j=1; j<=k; j++)
        {
            v[j]=cr[j];
           // printf("%.2lf %.2lf\n", cr[j].x, cr[j].y);
        }
    //    printf("\n");
        v[k+1]=v[1];
    }
  //  printf("%d\n", k);
    aria=0;
    for(i=1; i<=k; i++)
    {
        aria+=v[i].x*v[i+1].y-v[i+1].x*v[i].y;
    //    printf("%.2lf %.2lf\n", v[i].x, v[i].y);
    }
    aria/=2;
    if(aria<0) aria=-aria;
  //  printf("%.2lf", aria);
    return aria;
}

int main()
{
    freopen("camera.in", "r", stdin);
    freopen("camera.out", "w", stdout);
    scanf("%d", &n);
    for(i=1; i<=n; i++)
    {
        scanf("%lf%lf", &p[i].x, &p[i].y);
    }
    p[n+1]=p[1];
    semn=1;
    sol1=calc();
    semn=-1;
    sol2=calc();
    if(sol1>sol2) sol2=sol1;
    printf("%.2lf\n", sol2);
    return 0;
}