TIOJ-1510 彩色區塊

TIOJ-1510 彩色區塊

這題搞了好久=.=
要注意題目給的對角線座標，假設給(0,0)~(2,2) ，那只包含了4格!!!

AC code :

//By SCJ  

//tioj 1510 彩色區塊  

#include<bits/stdc++.h>  

using namespace std;  

int G[4][1005][1005];  

struct rgb{  

   int r,g,b;  

};  

map<rgb,int> mp;  

bool operator < (rgb a,rgb b)  

{  

   if(a.r!=b.r) return a.r<b.r;  

   if(a.g!=b.g) return a.g<b.g;  

   return a.b<b.b;  

}  

int main()  

{  

ios::sync_with_stdio(0);  

cin.tie(0);  

   int T;cin>>T;  

   while(T--)  

   {  

       int x1,x2,y1,y2,cr[4]={1};  

       cin>>x1>>y1>>x2>>y2>>cr[1]>>cr[2]>>cr[3];  

       if(x1>x2) swap(x1,x2);  

       if(y1>y2) swap(y1,y2);  

       for(int i=0;i<4;++i)  

       {  

           G[i][x1][y1]+=cr[i];  

           G[i][x2][y2]+=cr[i];  

           G[i][x1][y2]-=cr[i];  

           G[i][x2][y1]-=cr[i];  

       }  

   }  

   for(int k=0;k<4;++k)  

   {  

       for(int i=0;i<=1000;++i)  

           for(int j=1;j<=1000;++j)  

               G[k][i][j]+=G[k][i][j-1];  

       for(int j=0;j<=1000;++j)  

           for(int i=1;i<=1000;++i)  

               G[k][i][j]+=G[k][i-1][j];  

   }  

   int MAX=0;  

   for(int i=0;i<=1000;++i)  

   {  

       for(int j=0;j<=1000;++j)  

       {  

           if(G[0][i][j])  

           {  

               for(int h=1;h<4;++h)  

               {  

                   G[h][i][j]=ceil((double)G[h][i][j]/G[0][i][j]);  

               }  

               mp[{G[1][i][j],G[2][i][j],G[3][i][j]}]++;  

           }  

       }  

   }  

   rgb ans;  

   for(auto i:mp)  

       if(MAX<i.second) ans=i.first,MAX=i.second;  

   cout<<ans.r<<' '<<ans.g<<' '<<ans.b<<'\n';  

}