lib/Documentation/docs-sonyckson/p1.cpp

   1 #include <algorithm>
   2 #include <vector>
   3 #include <set>
   4 #include <string>
   5 #include <fstream>
   6 #include <iostream>
   7 #include <iomanip>
   8 #include <map>
   9 #include <sstream>
  10 #include <queue>
  11
  12 #include <cmath>
  13 #include <cstdio>
  14 #include <cctype>
  15 #include <cstdlib>
  16 #include <cstring>
  17
  18 #define forn(i, n) for(int i=0;i<int(n);i++)
  19 #define FOR(i, a, b) for(int i=(a);i<int(b);i++)
  20 #define RFOR(i, b, a) for(int i=(b);i>int(a);i--)
  21 #define foreach(it, c)  for(__typeof((c).begin()) it = (c).begin();it!=(c).end();++it)
  22 #define UNIQUE(a) SORT(a),(a).resize(unique(ALL(a))-a.begin())
  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 typedef long long ll;
  33 vector<pair<int,int> > POL;
  34 #define X first
  35 #define Y second
  36 bool inRange(double x, double x1, double x2){
  37         if( x > x1 && x < x2 ) return true;
  38         return false;
  39 }
  40 void print(pair<int,int> p){
  41 //      printf("  %i %i\n", p.first, p.second);
  42 }
  43 bool back(double x, double y){
  44         // primero contamos los q intersecan horizontales...
  45         int res = 0;
  46         int i,j ,k;
  47         int arriba, abajo, izq, der;
  48         arriba = abajo = izq = der = 0;
  49         for(i=0;i<POL.size();i++){
  50                 int i1 = i, i2 = (i+1)%POL.size();
  51                 if((double) POL[i1].second > y && POL[i1].second == POL[i2].second ){
  52                         if( inRange(x, min(POL[i1].X,POL[i2].X),max(POL[i1].X,POL[i2].X)) ){
  53                                 arriba++;
  54                         }
  55                 }else if( (double) POL[i1].second < y && POL[i1].second == POL[i2].second ){
  56                         print(POL[i1]),print(POL[i2]);
  57                         if( inRange(x, min(POL[i1].X,POL[i2].X),max(POL[i1].X,POL[i2].X)) ){
  58                                 abajo++;
  59                         }
  60                 }else if((double)POL[i1].X < x && POL[i1].X == POL[i2].X){
  61                         if(inRange(y,min(POL[i1].Y,POL[i2].Y), max(POL[i1].Y,POL[i2].Y))){
  62                                 izq++;
  63                         }
  64                 }else if((double)POL[i1].X > x && POL[i1].X == POL[i2].X){
  65                         if(inRange(y,min(POL[i1].Y,POL[i2].Y), max(POL[i1].Y,POL[i2].Y))){
  66                                 der++;
  67                         }
  68                 }
  69         }
  70         if(arriba && abajo &&  (arriba%2==0) && (abajo%2==0) ) return true;
  71         if(izq && der && (izq%2==0) && (der%2==0)) return true;
  72         return false;
  73 }
  74 bool vale(int x1, int x2, int y1, int y2 ){
  75         return back((double)(x1) + 0.5, (double)(y1+0.5) );
  76 }
  77
  78 int main(){
  79         int i, j, k;int casos;
  80         cin >> casos;
  81         for(int h = 0 ;h < casos; h ++ ){
  82                 int n;scanf("%i", &n);
  83                 POL.clear();
  84                 string s, t;
  85                 for(i=0;i<n;i++){
  86                         cin >> t >> k;
  87                         for(j=0;j<k;j++) s += t ;
  88                 }
  89                 int x, y; x = y = 0;
  90                 int dx[4] ={0, 1, 0, -1};
  91                 int dy[4] ={1, 0, -1, 0};
  92
  93                 int ind =  0;
  94                 POL.push_back(make_pair(0,0));
  95                 for(i=0;i<s.size();i++){
  96 //                      printf("%i %i %i   %c\n", x, y, ind, s[i]);
  97                         if( s[i] == 'F' ){
  98
  99                                 x += dx[ind], y+= dy[ind];
 100                         }if( s[i] == 'R' ){
 101                                 POL.PB(make_pair(x,y));
 102                                 ind = (ind+1)%4;
 103                         }if( s[i] == 'L' ){
 104                                 POL.PB(make_pair(x,y));
 105                                 ind = (ind+3)%4;
 106                         }
 107                 }
 108 //              for(i=0;i<POL.size();i++) printf("%i %i\n", POL[i].X, POL[i].Y);
 109                 vector<int> X, Y;
 110                 X.PB(4000);Y.PB(4000);
 111                 for(i=0;i<POL.size();i++){
 112                         X.PB(POL[i].first); Y.PB(POL[i].second);
 113                 }
 114                 UNIQUE(X), UNIQUE(Y);
 115                 sort(ALL(X));sort(ALL(Y));
 116                 int res = 0;
 117 //              for(i=0;i<X.size();i++) printf("%i ", X[i]);printf("\n");
 118 //              for(i=0;i<Y.size();i++) printf("%i  ", Y[i]);printf("\n");
 119 //              printf("%i %i\n", X.size(), Y.size());
 120                 for(i=0;i<(int)X.size()-1;i++)for(j=0;j<(int)Y.size()-1;j++){
 121
 122                         if( vale(X[i], X[i+1], Y[i], Y[i+1]) ){
 123                                 res += ( X[i+1]-X[i] ) * (Y[i+1]-Y[i]) ;
 124                         }
 125                 }
 126                 printf("Case #%i: %i\n", h+1, res);
 127         }return 0;
 128 }
 129
 130
 131
 132
 133
 134
 135