Computer Programming Contest Preparation

ToolBox - Source for: 108/10823/j1.c



/home/toolbox/public_html/solutions/108/10823/j1.c
    1 #include <stdio.h>
    2 #include <string.h>
    3 #include <sys/types.h>
    4 #include <sys/stat.h>
    5 #include <fcntl.h>
    6 #include <stdlib.h>
    7 #include <math.h>
    8 #include <stdint.h>
    9 
   10 #define TRUE  (1 == 1)
   11 #define FALSE (1 != 1)
   12 
   13 #define DEBUG if (FALSE)
   14 
   15 #define MAX_OBJECTS 111
   16 #define SQUARE 1
   17 #define CIRCLE 2
   18 
   19 /*
   20  *  Author: Isaac Traxler
   21  *    Date: 20120730
   22  * Purpose: Fun
   23  * Problem: Of Circles and Squares (10823)
   24  */
   25 
   26 struct colorStruct
   27 {
   28     /* STRUCT colorStruct */
   29     int R;
   30     int G;
   31     int B;
   32 }; /* STRUCT colorStruct */
   33 
   34 struct pointStruct
   35 {
   36     /* STRUCT pointStruct */
   37     int x;
   38     int y;
   39 }; /* STRUCT pointStruct */
   40 
   41 struct objectStruct
   42 {
   43     /* STRUCT objStruct */
   44     int knd;  /* 0 undefined, 1 square, 2 circle */
   45     struct pointStruct p;
   46     int lngth;
   47     struct colorStruct c;
   48 }; /* STRUCT objStruct */
   49 
   50 int numberOfTimes;
   51 int numObjects;
   52 int numQueries;
   53 struct objectStruct obj[MAX_OBJECTS];
   54 struct pointStruct queries[MAX_OBJECTS];
   55 
   56 void init()
   57 {
   58     /* FUNCTION init */
   59     scanf("%d ", &numberOfTimes);
   60 } /* FUNCTION init */
   61 
   62 void getInput()
   63 {
   64     /* FUNCTION getInput */
   65     int i;
   66     char kind[10];
   67 
   68     scanf(" %d %d ", &numObjects, &numQueries);
   69 
   70     /* get objects */
   71     for (i=0; i<numObjects; i++)
   72         {
   73             /* for each object */
   74             obj[i].knd = 0;
   75             scanf("%s %d %d %d %d %d %d ", kind, &obj[i].p.x, &obj[i].p.y, &obj[i].lngth, &obj[i].c.R, &obj[i].c.G, &obj[i].c.B);
   76             if ('S' == kind[0])
   77                 {
   78                     obj[i].knd = 1;
   79                 }
   80             else if ('C' == kind[0])
   81                 {
   82                     obj[i].knd = 2;
   83                 }
   84             else
   85                 {
   86                     exit(1);    /* bail if invalid input */
   87                 }
   88         } /* for each object */
   89 
   90     /* get query points -- this could be done one at a time in process */
   91     for (i=0; i<numQueries; i++)
   92         {
   93             /* load each query */
   94             scanf(" %d %d ", &queries[i].x, &queries[i].y);
   95         } /* load each query */
   96 } /* FUNCTION getInput */
   97 
   98 int onSquareBorder(int idx, struct pointStruct q)
   99 {
  100     /* FUNCTION onSquareBorder */
  101     int toReturn;
  102     /* check horizontals, then check verticals */
  103     toReturn = ((q.x >= obj[idx].p.x) &&
  104                 (q.x <= (obj[idx].p.x + obj[idx].lngth)) &&
  105                 ((q.y == obj[idx].p.y) || (q.y == (obj[idx].p.y + obj[idx].lngth))))
  106                ||
  107                ((q.y >= obj[idx].p.y) &&
  108                 (q.y <= (obj[idx].p.y + obj[idx].lngth)) &&
  109                 ((q.x == obj[idx].p.x) || (q.x == (obj[idx].p.x + obj[idx].lngth))));
  110     return toReturn;
  111 } /* FUNCTION onSquareBorder */
  112 
  113 int onCircleBorder(int idx, struct pointStruct q)
  114 {
  115     /* FUNCTION onCircleBorder */
  116     int toReturn;
  117     int d2;
  118 
  119     /* do distance as squares to avoid squareroot */
  120     d2 = obj[idx].lngth * obj[idx].lngth;
  121     /* if radius^2 == (x-px)^2 + (y-py)^2 then it is on border */
  122     toReturn = ((q.x-obj[idx].p.x)*(q.x-obj[idx].p.x) + (q.y-obj[idx].p.y)*(q.y-obj[idx].p.y) == d2);
  123     return toReturn;
  124 } /* FUNCTION onCircleBorder */
  125 
  126 int inSquare(int idx, struct pointStruct q)
  127 {
  128     /* FUNCTION inSquare */
  129     int toReturn;
  130 
  131     toReturn = (q.x > obj[idx].p.x) && (q.x < (obj[idx].p.x + obj[idx].lngth)) &&
  132                (q.y > obj[idx].p.y) && (q.y < (obj[idx].p.y + obj[idx].lngth));
  133     return toReturn;
  134 } /* FUNCTION inSquare */
  135 
  136 int inCircle(int idx, struct pointStruct q)
  137 {
  138     /* FUNCTION inCircle */
  139     int toReturn;
  140     int d2;
  141 
  142     /* do distance as squares to avoid squareroot */
  143     d2 = obj[idx].lngth * obj[idx].lngth;
  144     /* if radius^2 == (x-px)^2 + (y-py)^2 then it is on border */
  145     toReturn = (((q.x-obj[idx].p.x)*(q.x-obj[idx].p.x) + (q.y-obj[idx].p.y)*(q.y-obj[idx].p.y)) < d2);
  146     return toReturn;
  147 } /* FUNCTION inCircle */
  148 
  149 void process()
  150 {
  151     /* FUNCTION process */
  152     int i;
  153     int j;
  154     int boundary;
  155     int interior;
  156     struct colorStruct color;
  157     int colorCnt;
  158 
  159     for (i=0; i<numQueries; i++)
  160         {
  161             /* do each query */
  162             boundary = FALSE;
  163             for (j=0; (j<numObjects) && (!boundary); j++)
  164                 {
  165                     /* for each object */
  166                     if (SQUARE == obj[j].knd)
  167                         {
  168                             boundary = onSquareBorder(j, queries[i]);
  169                         }
  170                     if (CIRCLE == obj[j].knd)
  171                         {
  172                             boundary = onCircleBorder(j, queries[i]);
  173                         }
  174                 } /* for each object */
  175             if (boundary)
  176                 {
  177                     /* on boundary */
  178                     printf("(0, 0, 0)\n");
  179                 } /* on boundary */
  180             else
  181                 {
  182                     /* check interior */
  183                     color.R = 0;
  184                     color.G = 0;
  185                     color.B = 0;
  186                     colorCnt = 0;
  187                     for (j=0; j<numObjects; j++)
  188                         {
  189                             /* for each object */
  190                             interior = FALSE;
  191                             if (SQUARE == obj[j].knd)
  192                                 {
  193                                     /* check for inside SQUARE */
  194                                     interior = inSquare(j, queries[i]);
  195                                 }  /* check for inside SQUARE */
  196                             if (CIRCLE == obj[j].knd)
  197                                 {
  198                                     /* check for inside CIRCLE */
  199                                     interior = inCircle(j, queries[i]);
  200                                 } /* check for inside CIRCLE */
  201                             if (interior)
  202                                 {
  203                                     /* point is in interior of object */
  204                                     color.R = color.R + obj[j].c.R;
  205                                     color.G = color.G + obj[j].c.G;
  206                                     color.B = color.B + obj[j].c.B;
  207                                     colorCnt++;
  208                                 } /* point is in interior of object */
  209                         } /* for each object */
  210                     if (0 == colorCnt)
  211                         {
  212                             /* not inside any objects */
  213                             printf("(255, 255, 255)\n");
  214                         } /* not inside any objects */
  215                     else
  216                         {
  217                             /* inside 1 or more objects */
  218                             color.R = (color.R + (colorCnt / 2)) / colorCnt;
  219                             color.G = (color.G + (colorCnt / 2)) / colorCnt;
  220                             color.B = (color.B + (colorCnt / 2)) / colorCnt;
  221                             printf("(%d, %d, %d)\n", color.R, color.G, color.B);
  222                         } /* inside 1 or more objects */
  223                 } /* check interior */
  224         } /* do each query */
  225 } /* FUNCTION process */
  226 
  227 int main ()
  228 {
  229     /* main */
  230     int i;
  231 
  232     init();
  233     for (i=1; i<=numberOfTimes; i++)
  234         {
  235             /* while */
  236             if (1 != i)
  237                 {
  238                     printf("\n");
  239                 }
  240             getInput();
  241             printf("Case %d:\n", i);
  242             process();
  243         } /* while */
  244 
  245     return EXIT_SUCCESS;
  246 } /* main */
  247 
  248