Cod sursa(job #253256)

Utilizator 630r63Ilinca George Mihai 630r63 Data 5 februarie 2009 16:44:38
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 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;  
}