lib/Documentation/docs-sonyckson/NKMARS.cpp

   1 // INTERSECCIÖN DE AREAS DE RECTÄNGULOS CON SEGMENT TREES :D
   2 #include <algorithm>
   3 #include <vector>
   4 #include <set>
   5 #include <string>
   6 #include <fstream>
   7 #include <iostream>
   8 #include <iomanip>
   9 #include <map>
  10 #include <sstream>
  11 #include <queue>
  12 #include <cassert>
  13 #include <cmath>
  14 #include <cstdio>
  15 #include <cctype>
  16 #include <cstdlib>
  17 #include <cstring>
  18
  19 #define REP(i, n) for(int i=0;i<int(n);i++)
  20 #define FOR(i, a, b) for(int i=(a);i<int(b);i++)
  21 #define RFOR(i, b, a) for(int i=(b);i>int(a);i--)
  22 #define foreach(it, c)  for(__typeof((c).begin()) it = (c).begin();it!=(c).end();++it)
  23 #define ALL(x)   (x).begin(),(x).end()
  24 #define SIZE(x)   (int)(x).size()
  25 #define SORT(x) sort(ALL(x))
  26 using namespace std;
  27 #define VI vector<int>
  28 #define VS vector<string>
  29 #define PB push_back
  30 #define ISS istringstream
  31 #define OSS ostringstream
  32 #define MP make_pair
  33 typedef long long ll;
  34 struct node{
  35         int on,area;
  36         node(){}
  37         node(int x, int y){on=x,area=y;}
  38 };
  39 struct segmentTree{
  40         vector<node> vec;
  41         int off;
  42         segmentTree(int x){off=1;while(off<x)off*=2;vec.resize(off*2,node(0,0));}
  43         int superficie(){return vec[1].area;}
  44         void add(int node, int begin, int end, int a, int b){
  45                 if( begin > b || end < a ) return;
  46                 if( begin <= a && b <= end ){
  47                         if( !vec[node].on ){
  48                                 vec[node].area = b-a+1;
  49                         }vec[node].on++;
  50                 }else{
  51                         add(node*2,begin,end,a,(a+b)/2);
  52                         add(node*2+1,begin,end,(a+b)/2+1,b);
  53                         if(!vec[node].on)vec[node].area = vec[2*node].area+vec[2*node+1].area;
  54                 }
  55         }
  56         void take(int node,int begin,int end,int a, int b){
  57                 if( begin > b || end < a ) return;
  58                 if( begin <= a && b <= end ){
  59                         vec[node].on--;
  60                         if( !vec[node].on ){
  61                                 if(a!=b)vec[node].area = vec[node*2].area + vec[node*2+1].area;
  62                                 else vec[node].area = 0;
  63                         }
  64                 }else{
  65                         take(node*2,begin,end,a,(a+b)/2);
  66                         take(node*2+1,begin,end,(a+b)/2+1,b);
  67                         if(!vec[node].on)vec[node].area = vec[node*2].area + vec[node*2+1].area;
  68                 }
  69         }
  70 };
  71 #define PII pair<int,int>
  72 int main(){
  73         int i,j ,k;
  74         segmentTree sTree(30001);
  75         int N;scanf("%i", &N);
  76         int x1, y1, x2, y2;
  77         vector< pair<int,PII> > abre, cierra;
  78         int lastx=INT_MAX;
  79         for(i=0;i<N;i++){
  80                 scanf("%i %i %i %i", &x1, &y1, &x2, &y2);
  81                 y2--;
  82                 abre.PB(MP(x1,MP(y1,y2)));
  83                 cierra.PB(MP(x2,MP(y1,y2)));
  84                 lastx = min(x1,min(x2,lastx));
  85         }
  86         sort(ALL(abre)); sort(ALL(cierra));
  87         abre.PB(MP(INT_MAX,PII(0,0)));
  88         int ind1, ind2;
  89         ind1 = ind2 = 0;
  90         int res = 0;
  91         for(k=0;k<2*N;k++){
  92                 if( abre[ind1].first < cierra[ind2].first ){
  93                         res += sTree.superficie() * (abre[ind1].first-lastx);
  94                         lastx = abre[ind1].first;
  95                         sTree.add(1,abre[ind1].second.first, abre[ind1].second.second,0,sTree.off-1);
  96                         ind1++;
  97                 }else{
  98                         res += sTree.superficie()*(cierra[ind2].first-lastx);
  99                         lastx = cierra[ind2].first;
 100                         sTree.take(1,cierra[ind2].second.first, cierra[ind2].second.second,0,sTree.off-1);
 101                         ind2++;
 102                 }
 103         }
 104         printf("%i\n", res);
 105 }