Cod sursa(job #141168)

Utilizator SycronVene Tian Sycron Data 22 februarie 2008 20:11:14
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.64 kb
#include <stdio.h>   
#include <vector>   
using namespace std;   
  
#define NMAX 4010   
#define eps 1e-6   
#define INF 200000   
#define doubl double   
#define punct pair <doubl, doubl>   
#define x first   
#define y second   
  
inline doubl DABS(doubl x) { return (x < 0) ? -x : x; }   
inline doubl DMIN(doubl a, doubl b) { return (a < b) ? a : b; }   
inline doubl DMAX(doubl a, doubl b) { return (a > b) ? a : b; }   
inline int egal(doubl a, doubl b) { return DABS(a - b) <= eps; }   
  
int N;   
  
doubl xmin, xmax, ymin, ymax;   
  
punct A[NMAX];   
  
int nrez;   
punct rez[NMAX];   
int ncur;   
punct cur[NMAX];   
  
int semn(punct a, punct b, punct c)   
{   
    doubl q = a.first * (b.second - c.second) - a.second * (b.first - c.first) + b.first * c.second - b.second * c.first;   
    if (DABS(q) < eps) return 0;   
    if (q < 0) return -1;   
return 1;   
}   
  
int nr_inter_oriz(punct a, punct b, int lat)   
{   
    int nr = 0, i;   
  
    for (i = 0; i < N; i++)   
    {   
        if (i == lat) continue;   
        if (egal(a.second, A[i].second) || egal(a.second, A[i+1].second))    
        {   
            if (egal(A[i].second, A[i+1].second)) continue;   
            nr += egal(a.second, DMIN(A[i].second, A[i+1].second));   
            continue;   
        }   
        nr += semn(A[i], a, b) * semn(A[i+1], a, b) < 0 && semn(a, A[i], A[i+1]) * semn(b, A[i], A[i+1]) < 0;   
    }   
  
return nr;         
}   
int nr_inter_vert(punct a, punct b, int lat)   
{   
    int nr = 0, i;   
  
    for (i = 0; i < N; i++)   
    {   
        if (i == lat) continue;   
        if (egal(a.first, A[i].first) || egal(a.first, A[i+1].first))   
        {   
            if (egal(A[i].first, A[i+1].first)) continue;   
            nr += egal(a.first, DMIN(A[i].first, A[i+1].first));   
            continue;   
        }   
        nr += semn(A[i], a, b) * semn(A[i+1], a, b) < 0 && semn(a, A[i], A[i+1]) * semn(b, A[i], A[i+1]) < 0;   
    }   
return nr;   
}   
  
punct inter(punct A, punct B, punct C, punct D)   
{   
    doubl a1, b1, c1, a2, b2, c2;   
  
    a1 = A.second - B.second;   
    b1 = B.first - A.first;   
    c1 = - (A.first * B.second - A.second * B.first);   
  
    a2 = C.second - D.second;   
    b2 = D.first - C.first;   
    c2 = - (C.first * D.second - C.second * D.first);   
  
    punct aux;   
    aux.first = (c1 * b2 - b1 * c2) / (a1 * b2 - b1 * a2);   
    aux.second = (a1 * c2 - c1 * a2) / (a1 * b2 - b1 * a2);   
  
return aux;   
}   
  
double calc(int smn)   
{   
    int i, j;   
       
    nrez = 4;   
    rez[0].first = xmin; rez[0].second = ymin;   
    rez[1].first = xmax; rez[1].second = ymin;   
    rez[2].first = xmax; rez[2].second = ymax;   
    rez[3].first = xmin; rez[3].second = ymax;   
    rez[4] = rez[0];   
  
    punct mij, aux;   
    doubl w;   
    for (i = 0; i < N; i++)   
    {   
        int q, q1;   
        for (j = 0, ncur = 0; j < nrez; j++)   
        {   
            q = semn(rez[j], A[i], A[i+1]);   
            q1 = semn(rez[j+1], A[i], A[i+1]);   
  
            if (!q) cur[ncur++] = rez[j];   
            else  
            {   
                if (q == smn)    
                {   
                    cur[ncur++] = rez[j];   
                    if (q1 == -smn) cur[ncur++] = inter(rez[j], rez[j+1], A[i], A[i+1]);   
                }   
                else  
                {   
                    if (q1 == smn) cur[ncur++] = inter(rez[j], rez[j+1], A[i], A[i+1]);   
                }   
            }   
        }   
        cur[ncur] = cur[0];   
  
        nrez = ncur;   
        memcpy(rez, cur, sizeof(rez));   
           
        if (!nrez) break;   
    }   
  
    doubl ar = 0;   
  
    for (i = 0; i < ncur; i++)   
        ar += rez[i].first * rez[i+1].second - rez[i].second * rez[i+1].first;   
    ar *= 0.5;   
    return DABS(ar);   
}   
  
int main()   
{   
    int i;   
    xmin = INF, xmax = -INF, ymin = INF, ymax = -INF;   
       
    freopen("camera.in", "r", stdin);   
    freopen("camera.out", "w", stdout);   
  
    scanf("%d", &N);   
  
    for (i = 0; i < N; i++)   
    {   
        scanf("%lf %lf", &A[i].first, &A[i].second);   
        xmin = DMIN(xmin, A[i].first);   
        xmax = DMAX(xmax, A[i].first);   
        ymin = DMIN(ymin, A[i].second);   
        ymax = DMAX(ymax, A[i].second);        
    }   
    A[i] = A[0];   
       
    doubl ar1 = calc(1), ar2 = calc(-1);   
       
    printf("%0.2lf\n", DMAX(ar1, ar2));   
       
fclose(stdin);   
fclose(stdout);   
return 0;   
}