tr.cpp

PASCAL光盘资料PASCAL光盘资料PASCAL光盘资料

#include <fstream.h>
#include <string.h>
#include <stdlib.h>

ifstream fin("tr.in");
ofstream fout("tr.out");

const int MAX = 2000+5;

struct tr {
   int x, y, m;   
};

int n, line[MAX];
tr t[MAX];
double area = 0;

void init();
void solve();

main() {
   init();
   solve();

   fout.precision(1);
   fout.setf(ios::fixed, ios::floatfield);
   fout << area << endl;

   return 0;  
}

int cmp(const void* e1, const void* e2) {
   return *((const int*)e1) - *((const int*)e2);
}

void init() {
   int i, tmp;
   fin >> n;  
   for (i = 1; i <= n; i++) {
      fin >> t[i].x >> t[i].y >> t[i].m;
      line[i] = t[i].x + t[i].y + t[i].m;
   }
   qsort(&t[1], n, sizeof(t[0]), cmp);
   
   qsort(&line[1], n, sizeof(line[0]), cmp);
   for (line[0] = 0, i = 1; i <= n; i++)
      if (i == 1 || line[i] != line[i - 1])
         line[++line[0]] = line[i];
}

double cal(int l, int r, int h) {
   if (l >= r) return 0;
   int a1 = r - l, a2 = r - l - h;
   if (a2 < 0) a2 = 0, h = r - l;
   return 0.5 * (a1 + a2) * h;  
}

void solve() {
   int i, j, last = -1000000000, now;
   for (i = 1; i <= line[0]; i++, last = now) {
      now = line[i];
      int l = -100000000, r = -100000000;
      for (j = 1; j <= n; j++)
         if (t[j].x + t[j].y < now && t[j].x + t[j].y + t[j].m >= now) {
            int nl = t[j].x, nr = t[j].x + now - t[j].x - t[j].y;
            if (nr > r) {
               area += cal(l, r, now - last);
               area -= cal(nl, r, now - last);
               l = nl, r = nr;
            }
         }
      area += cal(l, r, now - last);
   }   
}