Cod sursa(job #290170)

Utilizator flamecataCiobanu Alexandru-Catalin flamecata Data 27 martie 2009 16:30:46
Problema Camera Scor 100
Compilator cpp Status done
Runda aa Marime 2.96 kb
 #include <cstdio>     
 #include <algorithm>     
 #include <cmath>     
      
 using namespace std;     
      
 #define Nmax 2048     
 #define INF 1000000     
 #define pct pair<double, double>     
 #define x first     
 #define y second     
 #define mp make_pair     
      
 const double eps = 1.0e-8;     
      
 int n, ct1, ct2;     
 pct p[Nmax], d1[Nmax], d2[Nmax];     
      
 void citire()     
 {     
     int i, a, b;     
          
     scanf("%d\n", &n);     
     for (i = 1; i <= n; ++i)     
     {     
         scanf("%d %d\n", &a, &b);     
         p[i] = mp(a, b);     
     }     
     p[n + 1] = p[1];     
 }     
      
 pct inter(double a1, double b1, double c1, double a2, double b2, double c2)     
 {     
     return mp( (b2 * c1 - b1 * c2) / (a2 * b1 - a1 * b2), (a1 * c2 - a2 * c1) / (a2 * b1 - a1 * b2));     
 }     
      
 void solve()     
 {     
     int i, j;     
     double a1, b1, c1, a2, b2, c2, arie = 0;     
          
     for (i = 1; i <= n; ++i)     
         arie += p[i].x * p[i + 1].y - p[i + 1].x * p[i].y;     
          
     if (arie > 0)     
         reverse(p+1, p+n+2);     
          
     d1[++ct1] = mp(-INF, -INF);     
     d1[++ct1] = mp(-INF, INF);     
     d1[++ct1] = mp(INF, INF);     
     d1[++ct1] = mp(INF, -INF);     
     d1[ct1 + 1] = d1[1];     
          
     for (i = 1; i <= n; ++i)     
     {     
         ct2 = ct1;     
         memcpy(d2, d1, sizeof(d1));     
         ct1 = 0;     
              
         a1 = p[i].y - p[i + 1].y;     
         b1 = p[i + 1].x - p[i].x;     
         c1 = p[i].x * p[i + 1].y - p[i + 1].x * p[i].y;     
              
         for (j = 1; j <= ct2; ++j)     
         {     
             a2 = d2[j].y - d2[j + 1].y;     
             b2 = d2[j + 1].x - d2[j].x;     
             c2 = d2[j].x * d2[j + 1].y - d2[j + 1].x * d2[j].y;     
                  
             if (a1 * d2[j].x + b1 * d2[j].y + c1 < eps)     
                 if (a1 * d2[j + 1].x + b1 * d2[j + 1].y + c1 < eps)     
                     d1[++ct1] = d2[j + 1];     
                 else     
                     d1[++ct1] = inter(a1, b1, c1, a2, b2, c2);     
             else     
                 if (a1 * d2[j + 1].x + b1 * d2[j + 1].y + c1 < eps)     
                 {     
                     d1[++ct1] = inter(a1, b1, c1, a2, b2, c2);     
                     d1[++ct1] = d2[j + 1];     
                 }     
         }     
         d1[ct1 + 1] = d1[1];     
     }     
          
     arie = 0;     
     for (i = 1; i <= ct1; ++i)     
         arie += d1[i].x * d1[i + 1].y - d1[i + 1].x * d1[i].y;     
          
     arie /= 2;     
     arie = fabs(arie);     
     printf("%.2lf\n", arie);     
 }     
      
 int main()     
 {     
     freopen("camera.in", "r", stdin);     
     freopen("camera.out", "w", stdout);     
     citire();     
     solve();     
     return 0;     
}