2008 TOI 研習營初選 TOI2008 5. 彩色區塊
作法 : 經由離散化資料後 來加速搜尋
當然 最暴力也會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;
}