摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : 經由離散化資料後  來加速搜尋

當然  最暴力也會AC的作法  放在最下面

怎麼離散化 邊長

這個部份由阿尼雅提供 http://www.matrix67.com/blog/archives/108

不一定要把邊長設定成1x1 只要加大邊長的設定  再跑的時候

相當快呢!

/************************************************************/

#include<stdlib.h>
#include<stdio.h>
main()
{
  int N;
  int x[201][2],y[201][2];
  int R[201],G[201],B[201];
  while(scanf("%d",&N)==1)
      {
         int AX[1001]={0},AY[1001]={0},a,b,c;
         for(a=0;a<N;a++)
           {
           scanf("%d %d %d %d %d %d %d",&x[a][0],&y[a][0],&x[a][1],&y[a][1],&R[a],&G[a],&B[a]);
            AX[x[a][0]]=1,AX[x[a][1]]=1;
            AY[y[a][0]]=1,AY[y[a][1]]=1;
           }
         int DisX[201],DisY[201],topx=0,topy=0,LASTx=0,LASTy=0;
         for(a=0;a<=1000;a++)
           {
            if(AX[a]==1)
              {
                  AX[a]=++topx;
                  DisX[topx]=-(LASTx-a);
                  LASTx=a;
              }
            if(AY[a]==1)
              {
                  AY[a]=++topy;
                  DisY[topy]=-(LASTy-a);
                  LASTy=a;
              }
           }
         int MAP[201][201][3]={0},t,T[201][201]={0};
         for(a=0;a<N;a++)
            {
               if(R[a]==0&&G[a]==0&&B[a]==0) continue;
               if(x[a][0]>x[a][1])
                 {t=x[a][0],x[a][0]=x[a][1],x[a][1]=t;}
               if(y[a][0]>y[a][1])
                 {t=y[a][0],y[a][0]=y[a][1],y[a][1]=t;}
               for(b=AX[x[a][0]]+1;b<=AX[x[a][1]];b++)
                  for(c=AY[y[a][0]]+1;c<=AY[y[a][1]];c++)
                     T[b][c]++,MAP[b][c][0]+=R[a],MAP[b][c][1]+=G[a],MAP[b][c][2]+=B[a];
            }
         int AC[10000][4]={0},top=0;
         for(a=1;a<=topx;a++)
              for(b=1;b<=topy;b++)
                if(T[a][b]!=0)
                   {
                     int RR,GG,BB;
                       RR=MAP[a][b][0]/T[a][b]+(MAP[a][b][0]%T[a][b]!=0);         
                       GG=MAP[a][b][1]/T[a][b]+(MAP[a][b][1]%T[a][b]!=0);         
                       BB=MAP[a][b][2]/T[a][b]+(MAP[a][b][2]%T[a][b]!=0);
                     for(c=0;c<top;c++)
                        if(AC[c][0]==RR&&AC[c][1]==GG&&AC[c][2]==BB)
                           {AC[c][3]+=(DisX[a]*DisY[b]);break;}
                     if(top==c)
                        {
                           AC[top][0]=RR,AC[top][1]=GG,AC[top][2]=BB;   
                           AC[top++][3]=DisX[a]*DisY[b];                        
                        }
                   }
          int TMAX=0,r,g;
          for(a=0;a<top;a++)
             if(TMAX<AC[a][3])
               {TMAX=AC[a][3],r=AC[a][0],g=AC[a][1],b=AC[a][2];}
           printf("%d %d %d\n",r,g,b);
      }
  return 0;
}

/************************************************************/

#include<stdlib.h>
#include<stdio.h>
int MAP[1001][1001][3];
int T[1001][1001];
int AC[1000000][4];
main()
{
  int N,a,b,c,t=0;
  while(scanf("%d",&N)==1)
     {
       int x1,x2,y1,y2,R,G,B,MAX=0;
        for(a=0;a<N;a++)
           {
            scanf("%d %d %d %d %d %d %d",&x1,&y1,&x2,&y2,&R,&G,&B);
            if(R==0&&G==0&&B==0) continue;
            if(x1>x2)
               {int t;t=x1,x1=x2,x2=t;}
            if(y1>y2)
               {int t;t=y1,y1=y2,y2=t;}
            for(b=x1;b<=x2;b++)
               for(c=y1;c<=y2;c++)
                  MAP[b][c][0]+=R,MAP[b][c][1]+=G,MAP[b][c][2]+=B,T[b][c]++;
            if(MAX<x2) MAX=x2;
            if(MAX<y2) MAX=y2;
           }
        int top=0;
        for(a=0;a<=MAX;a++)
              for(b=0;b<=MAX;b++)
                 if(T[a][b]!=0)
                    {
                       int R,G,B;
                       R=MAP[a][b][0]/T[a][b]+(MAP[a][b][0]%T[a][b]!=0);      
                       G=MAP[a][b][1]/T[a][b]+(MAP[a][b][1]%T[a][b]!=0);      
                       B=MAP[a][b][2]/T[a][b]+(MAP[a][b][2]%T[a][b]!=0);
                       for(c=0;c<top;c++)
                          if(AC[c][0]==R&&AC[c][1]==G&&AC[c][2]==B)
                             {AC[c][3]++;break;}
                       if(c==top)
                         {
                           AC[top][0]=R,AC[top][1]=G,AC[top][2]=B;
                           AC[top++][3]=1;
                         }
                    }
        int TMAX=0;
        for(a=0;a<top;a++)
           {
           if(AC[a][3]>TMAX)
             {TMAX=AC[a][3],R=AC[a][0],G=AC[a][1],B=AC[a][2];}
             AC[a][3]=0,AC[a][1]=0,AC[a][2]=0,AC[a][0]=0;
           }
        printf("%d %d %d\n",R,G,B);
        for(a=0;a<=MAX;a++)
           for(b=0;b<=MAX;b++)
             MAP[a][b][0]=0,MAP[a][b][1]=0,MAP[a][b][2]=0,T[a][b]=0;
     }
  return 0;
}