Problem D
Of Circles and Squares
Input: Standard Input

Output: Standard Output

We have placed a number of circles and squares on an infinite stretch of a 2D plane. These circles and squares come in various sizes and colors. But when we place more than one object together, the color in the common region of those objects becomes a mixture of the original color. We define the color of each geometric object by the 8 bit value of the Red, Green and Blue components. For example, a circle drawn in pure red would have the color (255,0,0). The borderline of each geometric object is drawn in black (0,0,0), and the empty spaces are always white (255,255,255). Given a number of such geometric objects and some points in the 2D plane, your task is to determine the color of the points. The color of a point is computed as the average red, average green and average blue values of the geometric objects that this point falls into. If the point is on the borderline of any of the geometric object, then its color would be black; if it falls in the empty space, the color of the point would be white.

Input

The first line of input gives you the number of test cases T (T≤100) to follow. Each test case starts with two integers, R and P. R (R≤100) is the number of geometric objects and P (P≤100) is the number of query points. Then there will be R lines describing the objects. The description of each geometric object follows the “object_type px py length r g b” format. object_type is the type of the geometric object, which can be “CIRCLE” or “SQUARE”. px and py (-1000≤px,py≤+1000) are two integers giving you the x and y coordinate of the center of the circle or the lower left corner of the square depending on the object type. length (0≤length≤2000) is the radius of the circle or the length of a side if it is a square. The r, g and b (0≤r,g,b≤255) values are integers giving you the color of the object. The description of the query points starts after the description of the objects. Each query point is denoted by an integer pair px and py (-1000≤px,py≤+1000) giving you the x and y coordinate of that point.

Output

For each test case, print the serial number of the test case first. Then for each of the query points, print the color of that point in one line. All the colors are to be rounded to the nearest integer (for example: 128.3 will be rounded to 128, 128.5 will be rounded to 129 and 128.7 will also be rounded to 129). There must be a blank line separating two test cases. Please consult the sample input/output section for the exact format.

Sample Input                                  Output for Sample Input

8 5

Problem setter: Monirul Hasan

Special Thanks: Shahriar Manzoor

有幾個特別的 Case 要注意

1. 在邊緣上一律黑色 (0, 0, 0), 不要跟其他的地方取平均

2. 記得四捨五入

3. 都不在任何裡面, 是白色 (255, 255, 255)

#include <stdio.h>
#include <math.h>
#define eps 1e-6
int main() {
    int t, cases = 0, n, m, i;
    char kind[150][50];
    double px[150], py[150], len[150], x, y;
    int r[150], g[150], b[150];
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &n, &m);
        for(i = 0; i < n; i++)
            scanf("%s %lf %lf %lf %d %d %d", kind[i], px+i, py+i
                  , len+i, r+i, g+i, b+i);
        printf("Case %d:\n", ++cases);
        while(m--) {
            scanf("%lf %lf", &x, &y);
            int ar = 0, ag = 0, ab = 0;
            int cnt = 0;
            for(i = 0; i < n; i++) {
                if(kind[i][0] == 'C') {
                    if(pow(px[i]-x, 2)+pow(py[i]-y, 2) <= len[i]*len[i]) {
                        if(fabs(pow(px[i]-x, 2)+pow(py[i]-y, 2) - len[i]*len[i]) < eps)
                            {ar = ag = ab = 0, cnt = 1;break;} // borderline
                        else
                            ar += r[i], ag += g[i], ab += b[i];
                        cnt++;
                    }
                } else {
                    if(px[i] <= x && x <= px[i]+len[i] && py[i] <= y && y <= py[i]+len[i]) {
                        if(fabs(x-px[i]) < eps || fabs(x-px[i]-len[i]) < eps ||
                           fabs(y-py[i]) < eps || fabs(y-py[i]-len[i]) < eps)
                           {ar = ag = ab = 0, cnt = 1;break;}
                        else
                            ar += r[i], ag += g[i], ab += b[i];
                        cnt++;
                    }
                }
            }
            if(cnt == 0)
                ar = ag = ab = 255, cnt++;
            if(ar%cnt*2 >= cnt)
                ar = ar/cnt+1;
            else
                ar /= cnt;
            if(ag%cnt*2 >= cnt)
                ag = ag/cnt+1;
            else
                ag /= cnt;
            if(ab%cnt*2 >= cnt)
                ab = ab/cnt+1;
            else
                ab /= cnt;
            printf("(%d, %d, %d)\n", ar, ag, ab);
        }
        if(t)   puts("");
    }
    return 0;
}