---
# System prepended metadata

title: TIOJ 1510 - 彩色區塊
tags: [TIOJ, TOI]

---

# TIOJ 1510 - 彩色區塊
###### tags: `TOI` `TIOJ`

### 題意

在 $(0≦X≦1000,0≦Y≦1000)$ 的平面上給定數個顏色不同的矩形區塊$(X1,Y1)至(X2,Y2)$，表示方式為 $(R,G,B)$ 且 $(0≦R≦255; 0≦G≦255; 0≦B≦255)$ ， $(R,G,B,X,Y∈Z)$。

且每個矩形有可能會有相互覆蓋的情形，假設一個整數座標為 $(x,y)$，被$k$個矩形覆蓋到，則此整數座標座標顏色為
$(\dfrac{1}{k}\sum_{i=1}^{k}R_i,\dfrac{1}{k}\sum_{i=1}^{k}G_i,\dfrac{1}{k}\sum_{i=1}^{k}B_i)$ ，若遇小數點採無條件進位法。

輸出分布面積最大(佔據最多個整數座標)之色彩的 R、G、B 即可。

### 解法
此題使用暴力法
1. 因為 $(0≦X≦1000,0≦Y≦1000)$ ，故可以開資料結購存取每個整數座標 $(x,y)$ 被矩形覆蓋到的的 R、G、B 值總和，除以被覆蓋矩形的數量後，再用 **ceil** 函式無條件進位就行。
2. 算完該整數座標的顏色後，用 **unordered_map<long long,int>** 來 **hash** 顏色，以「**R * 1000000 + G * 1000 + B**」來映射「**此顏色覆蓋的整數座標數**」。
3. 注意在計算每個整數座標的顏色時，若該點沒被覆蓋到則不要置入映射表內。
4. 遍歷映射表後取覆蓋最多的色彩，用 hash 值反推出 R、G、B 再輸出即可。

### code
```cpp=
#include <bits/stdc++.h>
using namespace std;

struct coor{
    double rec=0;
    int r=0,g=0,b=0;
    double rsum=0 , gsum=0 , bsum=0;
};

int n;
coor dot[1001][1001];
unordered_map <long long,int> color;

int main(){
    cin.tie(0);
    cin >> n;
    for(int i=0 ; i<n ; i++){
        double a,b,c;
        int xI , yI , xII , yII;
        cin >> xI >> yI >> xII >> yII;
        cin >> a >> b >> c;
        if(xI > xII) swap(xI,xII);
        if(yI > yII) swap(yI,yII);
        for(int j=xI ; j<xII ; j++){
            for(int k=yI ; k<yII ; k++){
                dot[j][k].rec++;
                dot[j][k].rsum += a;
                dot[j][k].gsum += b;
                dot[j][k].bsum += c;
            }
        }
    }

    for(int j=0 ; j<=1000 ; j++){
        for(int k=0 ; k<=1000 ; k++){
            if(dot[j][k].rsum == 0 && dot[j][k].gsum == 0 && dot[j][k].bsum == 0)
                continue;
            dot[j][k].r = ceil(dot[j][k].rsum / dot[j][k].rec);
            dot[j][k].g = ceil(dot[j][k].gsum / dot[j][k].rec);
            dot[j][k].b = ceil(dot[j][k].bsum / dot[j][k].rec);
            color[dot[j][k].r * 1000000 + dot[j][k].g * 1000 + dot[j][k].b]++;
        }
    }

    int maxColor = 0;
    int ansR , ansG , ansB;
    for(auto &it:color){
        if(it.first == 0) continue;
        if(it.second > maxColor){
            maxColor = it.second;
            ansB = it.first % 1000;
            ansG = (it.first % 1000000 - ansB ) / 1000;
            ansR = (it.first - ansB - ansG * 1000) / 1000000;
        }
    }

    cout << ansR << " " << ansG << " " << ansB << "\n";
    
}
```


