lib/Documentation/docs-sonyckson/rect1.cpp

   1 // GENERALIZACION RARA DE LA INTERSECCION DE RECTANGULOS::: PINTA RECT CON COLORES Y PIDE AREA DE CADA COLOR VISIBLE :)
   2
   3 /*
   4 ID: edestef1
   5 LANG: C++
   6 TASK: rect1
   7 */
   8 #include <map>
   9 #include <cstdio>
  10 #include <cstdlib>
  11 #include <vector>
  12 #include <algorithm>
  13 #include <utility>
  14 #include <sstream>
  15 #include <iostream>
  16 #include <set>
  17 using namespace std;
  18 FILE *fin, *fout;
  19 typedef struct{
  20         int x1, y1, x2, y2;
  21         int color;
  22 }rect;
  23 vector<rect> tod, aux;
  24
  25 int vale(rect &r){
  26         if( r.x1 == r.x2 || r.y1 == r.y2 ) return 0;
  27         return 1;
  28 }
  29 int agregar(rect r1, rect r2){
  30 //      printf("   %i %i %i %i %i\n", r2.x1, r2.x2, r2.y1, r2.y2, r2.color);
  31         if( r2.x1 >= r1.x2 || r2.x2 <= r1.x1 || r2.y1 >= r1.y2 || r2.y2 <= r1.y1 ) return 1;
  32         r2.x1 = max(r2.x1, r1.x1);
  33         r2.x2 = min(r2.x2, r1.x2);
  34         r2.y1 = max(r2.y1, r1.y1);
  35         r2.y2 = min(r2.y2, r1.y2);
  36
  37         rect u,d,t,c,s;
  38         u = r1;
  39         u.x2 = r2.x1;
  40         d.color = r1.color;
  41         d.x1 = r2.x1;d.x2 = r2.x2;
  42         d.y1 = r1.y1; d.y2 = r2.y1;
  43         t.color = r1.color;
  44         t.x1 = r2.x1;t.x2 = r2.x2;
  45         t.y1 = r2.y2; t.y2 = r1.y2;
  46 //      c = r2;
  47         s = r1;
  48         s.x1 = r2.x2;
  49
  50         if( vale(u) ) aux.push_back(u);
  51         if( vale(d) ) aux.push_back(d);
  52         if(vale(t) )aux.push_back(t);
  53 //      if(vale(c) ) aux.push_back(c);
  54         if( vale(s) )aux.push_back(s);
  55         return 0;
  56 }
  57 int main(){
  58         int i,j ,k;
  59         fin = fopen("rect1.in", "r"); fout = fopen("rect1.out", "w");
  60         int A, B, N;
  61         int color[2501];memset(color, 0, sizeof(color));
  62         fscanf(fin, "%i %i %i", &A, &B, &N);
  63         vector<int> X, Y;
  64         X.push_back(0), X.push_back(A);
  65         Y.push_back(0), Y.push_back(B);
  66         int arr[1001][5];
  67
  68         for(i=0;i<N;i++){
  69                 for(j=0;j<5;j++){
  70                         fscanf(fin, "%i", &arr[i][j]);
  71                 }
  72         }
  73
  74         tod.push_back((rect){0,0,A,B,1});
  75         for(i=0;i<N;i++){
  76                 aux.clear();
  77                 vector<rect> todAux;
  78                 rect r;
  79                 r.x1 = arr[i][0], r.y1 = arr[i][1], r.x2 = arr[i][2], r.y2 = arr[i][3], r.color = arr[i][4];
  80                 for(j=0;j<tod.size();j++){
  81                         if(agregar(tod[j], r))
  82                                 todAux.push_back(tod[j]);
  83                 }
  84                 tod = todAux;
  85                 for(j=0;j<aux.size();j++) tod.push_back(aux[j]);
  86                 tod.push_back(r);
  87         }
  88         for(i=0;i<tod.size();i++){
  89                 int tot = (tod[i].x2-tod[i].x1)*(tod[i].y2-tod[i].y1);
  90                 color[tod[i].color] += tot;
  91         }
  92         for(i=0;i<2501;i++){
  93                 if( color[i] ){
  94                         fprintf(fout, "%i %i\n", i, color[i]);
  95                         printf("%i %i\n", i, color[i]);
  96                 }
  97         }
  98         return 0;
  99 }