/home/toolbox/public_html/solutions/108/10823/tt.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 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 long x3 = x2-x;
68 long y3 = y2-y;
69 l = sqrt((double)(pow(x3,2)+pow(y3,2))); //distance formula
70 //l = sqrt((double)(x3*x3+y3*y3)); //distance formula
71 //l = sqrt((double)((x2-x)*(x2-x)+(y2-y)*(y2-y))); //distance formula
72 debug(l, TAB);
73 debug(s.length, endl);
74 if (pow(x3,2)+pow(y3,2) == pow((double)s.length,2)) return true;
75 return false;
76 }
77
78 bool is_bound_squa(shape s, point q)
79 {
80 if ((q.first == s.start_p.first && q.second >= s.start_p.second && q.second <= s.start_p.second + s.length) ||
81 (q.second == s.start_p.second && q.first >= s.start_p.first && q.first <= s.start_p.first + s.length))
82 return true;
83
84 return false;
85 }
86
87 bool is_in_circ(shape s, point q)
88 {
89 double l;
90 long x, y, x2, y2;
91 x = q.first;
92 y = q.second;
93 x2 = s.start_p.first;
94 y2 = s.start_p.second;
95 long x3 = x2-x;
96 long y3 = y2-y;
97 l = sqrt((double)(pow(x3,2)+pow(y3,2))); //distance formula
98 //l = sqrt((double)(x3*x3+y3*y3)); //distance formula
99 //l = sqrt((double)((x2-x)*(x2-x)+(y2-y)*(y2-y))); //distance formula
100 debug(l, TAB);
101 debug(s.length, endl);
102 if (pow(x3,2)+pow(y3,2) < pow((double)s.length,2)) return true;
103 return false;
104 }
105
106 bool is_in_squa(shape s, point q)
107 {
108 if (q.first > s.start_p.first && q.second > s.start_p.second &&
109 q.first < (s.start_p.first + s.length) && q.second < (s.start_p.second + s.length))
110 return true;
111 return false;
112 }
113
114 void dump()
115 {
116 //dump data
117 for (int i = 0; i < shapes.size(); ++i)
118 {
119 shape s = shapes[i];
120 debug(s.type, endl);
121 debug(s.start_p.first, endl);
122 debug(s.start_p.second, endl);
123 debug(s.length, endl);
124 debug(s.r, endl);
125 debug(s.g, endl);
126 debug(s.b, endl);
127 }
128 }
129
130 void getInput()
131 {
132 //get shapes and the number of queriers
133 scanf("%d %d", &num_shapes, &num_queries);
134 char sh_type[7];
135 int px, py, len, r, g, b;
136 while (num_shapes-- > 0)
137 {
138 memset(sh_type, 0, sizeof(sh_type));
139 px = py = len = r = g = b = 0;
140 scanf("%s %d %d %d %d %d %d", sh_type, &px, &py, &len, &r, &g, &b);
141 shape s;
142 s.type = sh_type;
143 s.start_p.first = px;
144 s.start_p.second = py;
145 s.length = len;
146 s.r = r;
147 s.g = g;
148 s.b = b;
149
150 shapes.push_back(s);
151 }
152 }
153
154 void process()
155 {
156 //process input
157 point q;
158 long r = 0, g = 0, b = 0;
159 bool done = false;
160 while (num_queries-- > 0)
161 {
162 scanf("%d %d", &q.first, &q.second);
163 //check boundaries
164 for (vector<shape>::iterator it = shapes.begin(); it != shapes.end(); ++it)
165 {
166 if (it->type == SQUARE)
167 {
168 done = is_bound_squa(*it, q);
169 if (done) debug("on square", endl);
170 }
171 else if (it->type == CIRCLE)
172 {
173 done = is_bound_circ(*it, q);
174 if (done) debug("on circle", endl);
175 }
176 if (done) break;
177 }
178 if (!done)
179 {
180 for (vector<shape>::iterator it = shapes.begin(); it != shapes.end(); ++it)
181 {
182 //reuse done for a different purpose, to say yes if point is in an object
183 if (it->type == SQUARE)
184 {
185 done = is_in_squa(*it, q);
186 if (done) debug("in square", endl);
187 }
188 else if (it->type == CIRCLE)
189 {
190 done = is_in_circ(*it, q);
191 if (done) debug("in circle", endl);
192 }
193
194 if (done) comp_shapes.push_back(*it);
195 done = false;
196 }
197
198 if (comp_shapes.size() == 0) r = g = b = 255; //not in a shape, so white
199 else
200 {
201 for (vector<shape>::iterator it = comp_shapes.begin(); it != comp_shapes.end(); ++it)
202 {
203 //average all
204 r += it->r;
205 g += it->g;
206 b += it->b;
207 }
208 debug(r, TAB);
209 debug(g, TAB);
210 debug(b, TAB);
211 debug(comp_shapes.size()-1, endl);
212 /*if (r != 0) r += comp_shapes.size()-1;
213 if (g != 0) g += comp_shapes.size()-1;
214 if (b != 0) b += comp_shapes.size()-1;*/
215 debug(r, TAB);
216 debug(g, TAB);
217 debug(b, endl);
218 /*r /= comp_shapes.size();
219 g /= comp_shapes.size();
220 b /= comp_shapes.size();*/
221 r = round1(r, comp_shapes.size());
222 g = round1(g, comp_shapes.size());
223 b = round1(b, comp_shapes.size());
224 /*size_t k = comp_shapes.size();
225 r = (int)(((double)r)/(double)k + 0.5);
226 g = (int)(((double)g)/(double)k + 0.5);
227 b = (int)(((double)b)/(double)k + 0.5);*/
228 }
229 }
230 printf("(%ld, %ld, %ld)\n", r, g, b);
231
232 r = g = b = 0;
233 comp_shapes.clear();
234 done = false;
235 }
236 }
237
238 int main()
239 {
240 scanf("%d", &num_cases);
241 int count = 0;
242 while (num_cases-- > 0)
243 {
244 ++count;
245 printf("Case %d:\n", count);
246 getInput();
247 //dump();
248 process();
249 if (num_cases > 0)
250 printf("\n");
251
252 //reset
253 comp_shapes.clear();
254 shapes.clear();
255 num_shapes = 0;
256 }
257
258 return 0;
259 }
260