1 /* C version of solution 1.
    2  *
    3  * Author: Matt Eastman
    4  */
    5 #include <assert.h>
    6 #include <ctype.h>
    7 #include <stdio.h>
    8 #include <stdlib.h>
    9 #include <string.h>
   10 
   11 #define FALSE 0
   12 #define TRUE 1
   13 
   14 typedef struct
   15   {
   16     int top;
   17     int left;
   18     int bottom;
   19     int right;
   20   } SubBox;
   21 
   22 typedef struct
   23   {
   24     char line[1024];
   25     SubBox* sub_boxes[3];
   26   } Box;
   27 
   28 SubBox* SubBox_New(int top, int left, int bottom, int right)
   29 {
   30   SubBox* box = (SubBox*)calloc(1, sizeof(SubBox));
   31   box->top = top;
   32   box->left = left;
   33   box->bottom = bottom;
   34   box->right = right;
   35   return box;
   36 }
   37 
   38 int SubBox_Touches(SubBox* a, SubBox* b)
   39 {
   40   if (a->top >= b->bottom &&
   41       a->bottom <= b->top &&
   42       a->left <= b->right &&
   43       a->right >= b->left)
   44     return TRUE;
   45   return FALSE;
   46 }
   47 
   48 void SubBox_Del(SubBox* box)
   49 {
   50   free(box);
   51 }
   52 
   53 Box* Box_New(char* line)
   54 {
   55   int top, left, bottom, right, line_size;
   56   Box* box = (Box*)calloc(1, sizeof(Box));
   57 
   58   strcpy(box->line, line);
   59   line_size = strlen(line);
   60   while (line_size > 0 && isspace(box->line[line_size - 1]))
   61     line_size--;
   62   box->line[line_size] = '\0';
   63 
   64   assert(sscanf(line, " %d,%d %d,%d", &top, &left, &bottom, &right) == 4);
   65   left = (left + 180) % 360;
   66   right = (right + 180) % 360;
   67 
   68   if (left > right)
   69     {
   70       box->sub_boxes[0] = SubBox_New(top, left, bottom, 360);
   71       box->sub_boxes[1] = SubBox_New(top, 0, bottom, right);
   72     }
   73   else if (left == 0)
   74     {
   75       box->sub_boxes[0] = SubBox_New(top, 360, bottom, 360);
   76       box->sub_boxes[1] = SubBox_New(top, 0, bottom, right);
   77     }
   78   else if (right == 0)
   79     {
   80       box->sub_boxes[0] = SubBox_New(top, left, bottom, 360);
   81       box->sub_boxes[1] = SubBox_New(top, 0, bottom, 0);
   82     }
   83   else
   84     {
   85       box->sub_boxes[0] = SubBox_New(top, left, bottom, right);
   86     }
   87 
   88   return box;
   89 }
   90 
   91 int Box_Touches(Box* a, Box* b)
   92 {
   93   int i, j;
   94   for (i = 0; a->sub_boxes[i] != NULL; i++)
   95     {
   96       for (j = 0; b->sub_boxes[j] != NULL; j++)
   97         {
   98           if (SubBox_Touches(a->sub_boxes[i], b->sub_boxes[j]))
   99             return TRUE;
  100         }
  101     }
  102   return FALSE;
  103 }
  104 
  105 void Box_Del(Box* box)
  106 {
  107   int i;
  108   for (i = 0; box->sub_boxes[i] != NULL; i++)
  109     {
  110       SubBox_Del(box->sub_boxes[i]);
  111     }
  112   free(box);
  113 }
  114 
  115 Box** ReadBoxList(int* num_boxes)
  116 {
  117   Box** boxes;
  118   char buf[1024];
  119   int i;
  120 
  121   assert(scanf(" %d ", num_boxes) == 1);
  122   boxes = (Box**)calloc(*num_boxes, sizeof(Box*));
  123   for (i = 0; i < *num_boxes; i++)
  124     {
  125       boxes[i] = Box_New(fgets(buf, sizeof(buf), stdin));
  126     }
  127   return boxes;
  128 }
  129 
  130 void FreeBoxList(Box** boxes, int num_boxes)
  131 {
  132   int i;
  133   for (i = 0; i < num_boxes; i++)
  134     {
  135       Box_Del(boxes[i]);
  136     }
  137   free(boxes);
  138 }
  139 
  140 int main(int argc, char** argv)
  141 {
  142   int num_cases, num_data_boxes, num_query_boxes;
  143   int case_num, i, j, num_matched;
  144   Box** data_boxes;
  145   Box** query_boxes;
  146 
  147   assert(scanf(" %d", &num_cases) == 1);
  148   for (case_num = 0; case_num < num_cases; case_num++)
  149     {
  150       if (case_num > 0)
  151         printf("\n");
  152 
  153       data_boxes = ReadBoxList(&num_data_boxes);
  154       query_boxes = ReadBoxList(&num_query_boxes);
  155 
  156       num_matched = 0;
  157       for (i = 0; i < num_data_boxes; i++)
  158         {
  159           for (j = 0; j < num_query_boxes; j++)
  160             {
  161               if (Box_Touches(data_boxes[i], query_boxes[j]))
  162                 {
  163                   printf("%s\n", data_boxes[i]->line);
  164                   num_matched++;
  165                   break;
  166                 }
  167             }
  168         }
  169       if (num_matched == 0)
  170         printf("No data found.\n");
  171 
  172       FreeBoxList(data_boxes, num_data_boxes);
  173       FreeBoxList(query_boxes, num_query_boxes);
  174     }
  175   return 0;
  176 }
  177