/home/toolbox/public_html/solutions/108/10823/z.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 SQUARE 'S'
18 /* 0 - interior, 1 - border, -1 exterior */
19 #define INTERIOR -1
20 #define BORDER 1
21 #define EXTERIOR 0
22
23 /*
24 * Author: Isaac Traxler
25 * Date: 20120730
26 * Purpose: Fun
27 * Problem: Of Circles and Squares (10823)
28 */
29
30 struct objectStruct
31 {
32 /* DEFINE objStruct */
33 char kind;
34 int px;
35 int py;
36 int lngth;
37 int r;
38 int g;
39 int b;
40 int r2; /* radius (lngth) squared */
41 int pxl; /* px + lngth */
42 int pyl; /* py + lngth */
43 }; /* DEFINE objStruct */
44
45 int numberOfTimes;
46 int numObjects;
47 int numQueries;
48 struct objectStruct obj[MAX_OBJECTS];
49 int qx[MAX_OBJECTS];
50 int qy[MAX_OBJECTS];
51 int R;
52 int G;
53 int B;
54 int cnt;
55 char dummy[8];
56
57 void getInput()
58 {
59 /* FUNCTION getInput */
60 int i;
61
62 scanf(" %d %d ", &numObjects, &numQueries);
63
64 /* get objects */
65 for (i=0; i<numObjects; i++)
66 {
67 /* for each object */
68 scanf("%c%s %d %d %d %d %d %d ", &obj[i].kind, dummy, &obj[i].px, &obj[i].py, &obj[i].lngth, &obj[i].r, &obj[i].g, &obj[i].b);
69 obj[i].r2 = obj[i].lngth * obj[i].lngth;
70 obj[i].pxl = obj[i].px + obj[i].lngth;
71 obj[i].pyl = obj[i].py + obj[i].lngth;
72 } /* for each object */
73
74 /* get query points -- this could be done one at a time in process */
75 for (i=0; i<numQueries; i++)
76 {
77 /* load each query */
78 scanf(" %d %d ", &qx[i], &qy[i]);
79 } /* load each query */
80 } /* FUNCTION getInput */
81
82 int testSquare(int idx, int x, int y)
83 {
84 /* FUNCTION testSquare */
85 int toReturn = EXTERIOR;
86
87 if ((x > obj[idx].px) && (x < obj[idx].pxl) && (y > obj[idx].py) && (y < obj[idx].pyl))
88 {
89 /* we have an interior point */
90 toReturn = INTERIOR;
91 } /* we have an interior point */
92 else
93 {
94 /* now check for border */
95 if (((x >= obj[idx].px) && (x <= obj[idx].pxl) && ((y == obj[idx].py) || (y == obj[idx].pyl))) ||
96 ((y > obj[idx].py) && (y < obj[idx].pyl) && ((x == obj[idx].px) || (x == obj[idx].pxl))))
97 {
98 /* on square */
99 toReturn = BORDER;
100 } /* on square */
101 } /* now check for border */
102 return toReturn;
103 } /* FUNCTION testSquare */
104
105 int testCircle(int idx, int x, int y)
106 {
107 /* FUNCTION testCircle */
108 int tmp;
109 int toReturn = EXTERIOR;
110
111 tmp = (x-obj[idx].px)*(x-obj[idx].px) + (y-obj[idx].py)*(y-obj[idx].py);
112 if (tmp < obj[idx].r2)
113 {
114 /* inside circle */
115 toReturn = INTERIOR;
116 } /* inside circle */
117 else
118 {
119 /* on circle */
120 if (tmp == obj[idx].r2)
121 toReturn = BORDER;
122 } /* on circle */
123 return toReturn;
124 } /* FUNCTION testCircle */
125
126 void process()
127 {
128 /* FUNCTION process */
129 int i;
130 int j;
131 int boundary;
132 int notOutside;
133
134 for (i=0; i<numQueries; i++)
135 {
136 /* do each query */
137 boundary = FALSE;
138 R = G = B = cnt = 0;
139 /* check each object against the query -- bail out early when a query is on the object */
140 for (j=0; (j<numObjects) && (!boundary); j++)
141 {
142 /* for each object */
143 if (SQUARE == obj[j].kind)
144 {
145 /* we have a square */
146 notOutside = testSquare(j, qx[i], qy[i]);
147 } /* we have a square */
148 else
149 {
150 /* we must have a circle */
151 notOutside = testCircle(j, qx[i], qy[i]);
152 } /* we must have a circle */
153 if (notOutside)
154 {
155 /* really all we know now is that it is not exterior */
156 if (INTERIOR == notOutside)
157 {
158 /* inside -- not on boundary */
159 R += obj[j].r;
160 G += obj[j].g;
161 B += obj[j].b;
162 cnt++;
163 } /* inside -- not on boundary */
164 else
165 boundary = TRUE;
166 } /* really all we know now is that it is not exterior */
167 } /* for each object */
168 if (boundary)
169 {
170 /* on boundary */
171 printf("(0, 0, 0)\n");
172 } /* on boundary */
173 else
174 {
175 /* point in interior(s) */
176 if (0 == cnt)
177 {
178 /* not inside any objects */
179 printf("(255, 255, 255)\n");
180 } /* not inside any objects */
181 else
182 {
183 /* inside 1 or more objects */
184 R = (2 * R + cnt) / (2 * cnt);
185 G = (2 * G + cnt) / (2 * cnt);
186 B = (2 * B + cnt) / (2 * cnt);
187 printf("(%d, %d, %d)\n", R, G, B);
188 } /* inside 1 or more objects */
189 } /* point in interior(s) */
190 } /* do each query */
191 } /* FUNCTION process */
192
193 int main ()
194 {
195 /* main */
196 int i;
197
198 scanf("%d ", &numberOfTimes);
199 for (i=1; i<=numberOfTimes; i++)
200 {
201 /* while */
202 if (1 != i)
203 {
204 printf("\n");
205 }
206 getInput();
207 printf("Case %d:\n", i);
208 process();
209 } /* while */
210
211 return EXIT_SUCCESS;
212 } /* main */
213
214