/home/toolbox/public_html/solutions/108/10823/ofcands.cpp
1 #include <cstdio>
2 #include <iostream>
3 #include <vector>
4 #include <cstring>
5 #include <cstdlib>
6 #include <cmath>
7
8 using namespace std;
9
10 #define DEBUG
11 #undef DEBUG //uncomment this line to pull out print statements
12 #ifdef DEBUG
13 #define TAB '\t'
14 #define debug(a, end) cout << #a << ": " << a << end
15 #else
16 #define debug(a, end)
17 #endif
18
19 typedef pair<int, int> point;
20 typedef long long int64; //for clarity
21 typedef vector<int> vi; //?
22 typedef vector<point> vp; //?
23 template<class T> void chmin(T &t, T f)
24 {
25 if (t > f) t = f; //change min
26 }
27 template<class T> void chmax(T &t, T f)
28 {
29 if (t < f) t = f; //change max
30 }
31
32 #define UN(v) SORT(v),v.erase(unique(v.begin(),v.end()),v.end())
33 #define SORT(c) sort((c).begin(),(c).end())
34 #define FOR(i,a,b) for (int i=(a); i < (b); i++)
35 #define REP(i,n) FOR(i,0,n)
36 #define CL(a,b) memset(a,b,sizeof(a))
37 #define CL2d(a,b,x,y) memset(a, b, sizeof(a[0][0])*x*y)
38
39 int round1(int p, int q) /* Rounds fraction p/q */
40 {
41 return (p / q) + (((2 * (p % q)) >= q) ? 1 : 0);
42 }
43
44 struct shape
45 {
46 point start_p;
47 int length;
48 string type;
49 long r, g, b;
50 };
51
52 /*global variables*/
53 int num_cases, num_shapes, num_queries;
54 vector<shape> shapes;
55 vector<shape> comp_shapes;
56 const string SQUARE = "SQUARE", CIRCLE = "CIRCLE";
57 /*global variables*/
58
59 bool is_bound_circ(shape s, point q)
60 {
61 double l;
62 long long x, y, x2, y2;
63 x = q.first;
64 y = q.second;
65 x2 = s.start_p.first;
66 y2 = s.start_p.second;
67 l = sqrt((double)(((x2-x)*(x2-x))+((y2-y)*(y2-y)))); //distance formula
68 debug(l, TAB);
69 debug(s.length, endl);
70 if (l == (double)s.length) return true;
71 return false;
72 }
73
74 bool is_bound_squa(shape s, point q)
75 {
76 if (((q.first == s.start_p.first || q.first == s.start_p.first+s.length) && q.second >= s.start_p.second && q.second <= s.start_p.second + s.length) ||
77 ((q.second == s.start_p.second || q.second == s.start_p.second+s.length) && q.first >= s.start_p.first && q.first <= s.start_p.first + s.length))
78 return true;
79
80 return false;
81 }
82
83 bool is_in_circ(shape s, point q)
84 {
85 double l;
86 long long x, y, x2, y2;
87 x = q.first;
88 y = q.second;
89 x2 = s.start_p.first;
90 y2 = s.start_p.second;
91 l = sqrt((double)(((x2-x)*(x2-x))+((y2-y)*(y2-y)))); //distance formula
92 debug(l, TAB);
93 debug(s.length, endl);
94 if (l < (double)s.length) return true;
95 return false;
96 }
97
98 bool is_in_squa(shape s, point q)
99 {
100 if (q.first > s.start_p.first && q.second > s.start_p.second &&
101 q.first < (s.start_p.first + s.length) && q.second < (s.start_p.second + s.length))
102 return true;
103 return false;
104 }
105
106 void dump()
107 {
108 //dump data
109 for (int i = 0; i < shapes.size(); ++i)
110 {
111 shape s = shapes[i];
112 debug(s.type, endl);
113 debug(s.start_p.first, endl);
114 debug(s.start_p.second, endl);
115 debug(s.length, endl);
116 debug(s.r, endl);
117 debug(s.g, endl);
118 debug(s.b, endl);
119 }
120 }
121
122 void getInput()
123 {
124 //get shapes and the number of queriers
125 scanf("%d %d", &num_shapes, &num_queries);
126 char sh_type[7];
127 int px, py, len, r, g, b;
128 while (num_shapes-- > 0)
129 {
130 scanf("%s %d %d %d %d %d %d", sh_type, &px, &py, &len, &r, &g, &b);
131 shape s;
132 s.type = sh_type;
133 s.start_p.first = px;
134 s.start_p.second = py;
135 s.length = len;
136 s.r = r;
137 s.g = g;
138 s.b = b;
139
140 shapes.push_back(s);
141 }
142 }
143
144 void process()
145 {
146 //process input
147 point q;
148 long r = 0, g = 0, b = 0;
149 bool done = false;
150 while (num_queries-- > 0)
151 {
152 scanf("%d %d", &q.first, &q.second);
153 //check boundaries
154 for (vector<shape>::iterator it = shapes.begin(); it != shapes.end(); ++it)
155 {
156 if (it->type == SQUARE)
157 {
158 done = is_bound_squa(*it, q);
159 if (done) debug("on square", endl);
160 }
161 else if (it->type == CIRCLE)
162 {
163 done = is_bound_circ(*it, q);
164 if (done) debug("on circle", endl);
165 }
166 if (done) break;
167 }
168 if (!done)
169 {
170 for (vector<shape>::iterator it = shapes.begin(); it != shapes.end(); ++it)
171 {
172 //reuse done for a different purpose, to say yes if point is in an object
173 if (it->type == SQUARE)
174 {
175 done = is_in_squa(*it, q);
176 if (done) debug("in square", endl);
177 }
178 else if (it->type == CIRCLE)
179 {
180 done = is_in_circ(*it, q);
181 if (done) debug("in circle", endl);
182 }
183
184 if (done) comp_shapes.push_back(*it);
185 done = false;
186 }
187
188 if (comp_shapes.size() == 0) r = g = b = 255; //not in a shape, so white
189 else
190 {
191 for (vector<shape>::iterator it = comp_shapes.begin(); it != comp_shapes.end(); ++it)
192 {
193 //average all
194 r += it->r;
195 g += it->g;
196 b += it->b;
197 }
198 debug(r, TAB);
199 debug(g, TAB);
200 debug(b, TAB);
201 debug(comp_shapes.size()-1, endl);
202 /*if (r != 0) r += comp_shapes.size()-1;
203 if (g != 0) g += comp_shapes.size()-1;
204 if (b != 0) b += comp_shapes.size()-1;*/
205 debug(r, TAB);
206 debug(g, TAB);
207 debug(b, endl);
208 /*r /= comp_shapes.size();
209 g /= comp_shapes.size();
210 b /= comp_shapes.size();*/
211 r = round1(r, comp_shapes.size());
212 g = round1(g, comp_shapes.size());
213 b = round1(b, comp_shapes.size());
214 }
215 }
216 printf("(%ld, %ld, %ld)\n", r, g, b);
217
218 r = g = b = 0;
219 comp_shapes.clear();
220 done = false;
221 }
222 }
223
224 int main()
225 {
226 scanf("%d", &num_cases);
227 int count = 0;
228 while (num_cases-- > 0)
229 {
230 ++count;
231 printf("Case %d:\n", count);
232 getInput();
233 //dump();
234 process();
235 if (num_cases > 0)
236 printf("\n");
237
238 //reset
239 comp_shapes.clear();
240 shapes.clear();
241 }
242
243 return 0;
244 }
245