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