Cod sursa(job #841464)

Utilizator stoicatheoFlirk Navok stoicatheo Data 24 decembrie 2012 11:53:59
Problema Camera Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 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;
}