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