Documentation/docs-sonyckson/3856.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 ALL(x)   (x).begin(),(x).end()
  23 #define SIZE(x)   (int)(x).size()
  24 #define SORT(x) sort(ALL(x))
  25 using namespace std;
  26 #define VI vector<int>
  27 #define VS vector<string>
  28 #define PB push_back
  29 #define ISS istringstream
  30 #define OSS ostringstream
  31 typedef long long ll;
  32 // NUNCA DEFINIR int max....
  33 #define M 100000
  34 class point{
  35         public:
  36                 double x, y;
  37                 point(){};
  38                 point(double xx, double yy){x=xx,y=yy;}
  39 };
  40 class object{
  41         public:
  42                 string tipo;
  43                 point p1, p2;
  44                 object(){};
  45 };
  46 object objects[110];
  47 bool mark[110];
  48 #define D double
  49 #define EPS 1e-9
  50 #define SQ(a)  (a*a)
  51 int N;
  52 D X, Y;
  53 bool inRange(double x, double mx, double Mx){
  54         if( x+EPS > mx && x < Mx+EPS ) return true;
  55         return false;
  56 }
  57 void print(point p){
  58 //      printf("%lf %lf\n", p.x, p.y);
  59 }
  60 bool intersect(point p1, point p2, int ind){
  61         D A1, B1, C1, A2, B2, C2;
  62         A1 = p2.y - p1.y, B1 = p1.x - p2.x;C1 = A1 * p1.x + B1 * p1.y;
  63         object O = objects[ind];
  64         A2 = O.p2.y - O.p1.y, B2 = O.p1.x - O.p2.x; C2 = A2 * O.p1.x + B2 * O.p1.y;
  65         print(p1) , print(p2), print(O.p1), print(O.p2);
  66         D det = A1 * B2 - B1 * A2;
  67         X =  ( C1 * B2 - C2 * B1 ) / det;
  68         Y =  ( A1 * C2 - A2 * C1 ) / det;
  69         print(point(X,Y));
  70         if( inRange(X, min(O.p1.x, O.p2.x) , max(O.p2.x, O.p1.x)) ){
  71                 if( inRange(Y,min(O.p1.y,O.p2.y), max(O.p1.y,O.p2.y)) )
  72                         return true;
  73         }
  74 //      printf("y no..\n");
  75         return false;
  76 }
  77
  78 bool EQ(double a, double b){if( fabs(a-b) < EPS ) return true; return false;}
  79 double dist(point p1, point p2){
  80         double x = p2.x-p1.x, y = p2.y - p1.y;
  81         return sqrt(x*x+y*y);
  82 }
  83 int cruz(point p1, point p2, point p3){
  84         double x1, y1, x2, y2;
  85         x1 = p2.x-p1.x, y1 = p2.y - p1.y;
  86         x2 = p3.x-p1.x, y2 = p3.y - p1.y;
  87         double det = x1*y2-x2*y1;
  88         if( det >0. ) return 1;
  89         return -1;
  90 }
  91 void back(D x1, D y1, D x2, D y2, int last){
  92 //      printf("%lf %lf %lf %lf %i\n", x1, y1, x2, y2, last);
  93         int i,j ,k;
  94         point p;
  95         int have = 0;
  96         int ind;
  97         point aux(x1+(y2-y1), y1+(x2-x1));
  98         int sign = cruz(point(x1,y1), aux, point(x2,y2));
  99         for(i=0;i<N;i++){
 100                 if( i == last ) continue;
 101                 if(intersect(point(x1,y1), point(x2,y2), i) ){
 102                         double d1, d2;
 103                         d1 = dist(point(X,Y), point(x1,y1)), d2 = dist(point(x1,y1),point(x2,y2));
 104 //                      if( EQ(d1+d2, dist(point(X,Y), point(x2,y2))) ) continue;
 105                         if( cruz(point(x1,y1),aux,point(X,Y)) != sign ) continue;
 106                         if( have ){
 107                                 if( dist(point(x1,y1),point(X,Y)) < dist(point(x1,y1),p) ) p = point(X,Y), ind = i;
 108                         }else{
 109                                 have = 1;
 110                                 p = point(X,Y);
 111                                 ind = i;
 112                         }
 113                 }
 114         }
 115         if( !have ) return;
 116         object O = objects[ind];
 117         if ( O.tipo == "D" ){
 118                 mark[ind] = true;
 119                 return;
 120         }if( O.tipo == "M" ){
 121                 D A1, B1, C1, A2, B2, C2;
 122                 A1 = O.p2.y - O.p1.y, B1 = O.p1.x-O.p2.x; C1 = A1 * O.p1.x + B1 * O.p1.y ;
 123                 swap(A1, B1);
 124                 A1 *= -1.;
 125                 C1 = A1 * p.x + B1 * p.y ;
 126                 A2 = O.p2.y - O.p1.y, B2 = O.p1.x-O.p2.x; C2 = A2 * x1 + B2 * y1 ;
 127                 D det = A1 * B2 - B1 * A2;
 128                 X =  ( C1 * B2 - C2 * B1 ) / det;
 129                 Y =  ( A1 * C2 - A2 * C1 ) / det;
 130                 point P;
 131                 P.x = X + X-x1;
 132                 P.y = Y + Y-y1;
 133                 back(p.x,p.y,P.x, P.y,ind);
 134                 return;
 135         }
 136         // SI TENEMOS UN SPLITTER:
 137         // buscamos la perpendicular al segmento del objeto y lo ponemos en A1, B1, C1...
 138         D A1, B1, C1, A2, B2, C2;
 139         A1 = O.p2.y - O.p1.y, B1 = O.p1.x-O.p2.x; C1 = A1 * O.p1.x + B1 * O.p1.y ;
 140         swap(A1, B1);
 141         A1 *= -1.;
 142         C1 = A1 * p.x + B1 * p.y ;
 143         A2 = O.p2.y - O.p1.y, B2 = O.p1.x-O.p2.x; C2 = A2 * x1 + B2 * y1 ;
 144
 145         D det = A1 * B2 - B1 * A2;
 146         X =  ( C1 * B2 - C2 * B1 ) / det;
 147         Y =  ( A1 * C2 - A2 * C1 ) / det;
 148
 149         point P;
 150         P.x = X + X-x1;
 151         P.y = Y + Y-y1;
 152         back(p.x,p.y,P.x, P.y,ind);
 153         back(p.x, p.y, p.x+(x2-x1), p.y + (y2-y1) ,ind);
 154 }
 155 int main(){
 156         int i,j ,k;
 157         int casos;scanf("%i", &casos);
 158         char arr[4];
 159
 160         for(int h =0  ; h < casos; h ++ ){
 161                 double x1, y1, x2, y2;
 162                 scanf("%lf,%lf %lf,%lf", &x1, &y1, &x2, &y2);
 163                 scanf("%i", &N);
 164                 for(i=0;i<N;i++){
 165                         string s; double x1, y1, x2, y2;
 166                         char c;
 167                         scanf("%s", arr);
 168                         s += arr[0];
 169                         scanf("%lf,%lf %lf,%lf", &x1, &y1, &x2, &y2);
 170                         objects[i].tipo = s;
 171                         objects[i].p1 = point(x1,y1);
 172                         objects[i].p2 = point(x2,y2);
 173                 }
 174                 memset(mark, false, sizeof(mark));
 175                 back(x1,y1,x2+x1,y2+y1, -1);
 176                 vector<int> res;
 177                 for(i=0;i<N;i++) if( mark[i]  && objects[i].tipo == "D" ) res.push_back(i);
 178                 printf("DATA SET #%i\n", h+1);
 179                 if( res.size()){
 180                         for(i=0;i<res.size();i++) printf("%i\n", 1+res[i]);
 181                 }else printf("NO BEAMS DETECTED\n");
 182         }return 0;
 183 }