help with shaping regions!!!

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:

help with shaping regions!!!

Post by midra »

I need help with this usaco problem (shaping regions)
I see the hint, and I did my best...
But my code is awful and I don't know another way to do it...
I think the idea is not wrong but my codes produce wrong answer for the third test.
here is my code...(I know it is ugly)

Code: Select all

#include <stdio.h>
int llx[5003],lly[5003],urx[5003],ury[5003],color[5003],area[2503];
int i,j,tmplx,tmply,tmpux,tmpuy,tmpc,ti;

void intersect(){
    tmplx=llx[j];tmply=lly[j];tmpux=urx[j];tmpuy=ury[j],tmpc=color[j];
     if (llx[ti]<=llx[j]){
        if(lly[ti]<=lly[j]){
           if(urx[ti]>=llx[j] && urx[ti]<=urx[j]){
              if(ury[ti]>=lly[j] && ury[ti]<=ury[j]){
                 lly[j]=ury[ti];
                 i++;
                 llx[i]=urx[ti];lly[i]=tmply;
                 urx[i]=urx[j];ury[i]=ury[ti];
                 color[i]=color[j];             
              }
              else if(ury[ti]>=lly[j] && ury[ti]>=ury[j])
                llx[j]=urx[ti];
           }
           else if(urx[ti]>=llx[j] && urx[ti]>=urx[j]){
              if(ury[ti]>=lly[j] && ury[ti]<=ury[j])
                 lly[j]=ury[ti];
              else if(ury[ti]>=lly[j] && ury[ti]>=ury[j])
                 llx[j]=urx[j]+1;
           }
        }
        else if (lly[ti]>=lly[j] && lly[ti]<=ury[j]){
            if(urx[ti]<=urx[j] && ury[ti]<=ury[j]){
               lly[j]=ury[ti];
               i++;
               llx[i]=tmplx;lly[i]=tmply;
               urx[i]=tmpux;ury[i]=lly[ti];
               color[i]=color[j];
               i++;
               llx[i]=urx[ti];lly[i]=lly[ti];
               urx[i]=tmpux;ury[i]=ury[ti];
               color[i]=color[j];
            }
            else if (urx[ti]<=urx[j] && ury[ti]>=ury[j]){
               urx[j]=urx[ti];ury[j]=lly[ti];
               i++;
               llx[i]=urx[i-1];lly[i]=tmply;
               urx[i]=tmpux;ury[i]=tmpuy;
               color[i]=color[j];
            }
            else if (urx[ti]>=urx[j] && ury[ti]<=ury[j]){
               ury[j]=lly[ti];
               i++;
               llx[i]=tmplx;lly[i]=ury[ti];
               urx[i]=tmpux;ury[i]=tmpuy;
               color[i]=color[j];
            }
            else if (urx[ti]>=urx[j] && ury[ti]>=ury[j])
               ury[j]=lly[ti];
       }
     }
     else if(llx[ti]>=llx[j]){
        if(lly[ti]<=lly[j]){
           if(urx[ti]<=urx[j]){
              if(ury[ti]<=ury[j]){
                 lly[j]=ury[ti];
                 i++;
                 llx[i]=tmplx;lly[i]=tmply;
                 urx[i]=llx[ti];ury[i]=ury[ti];
                 color[i]=color[j];
                 i++;
                 llx[i]=urx[ti];lly[i]=tmply;  //llx[i]=tmplx;
                 urx[i]=tmpux;ury[i]=ury[ti];//ury[i]=lly[j];
                 color[i]=color[j];
              }
              else if(ury[ti]>=ury[j]){
                 urx[j]=llx[ti];
                 i++;
                 llx[i]=urx[ti];lly[i]=tmply;
                 urx[i]=tmpux;ury[i]=tmpuy;
                 color[i]=color[j];
              }
           }
           else if(urx[ti]>=urx[j]){
              if(ury[ti]>=ury[j])
                urx[j]=llx[ti];
              else if(ury[ti]<=ury[j]){
                urx[j]=llx[ti];
                i++;
                llx[i]=llx[ti];lly[i]=ury[ti];
                urx[i]=tmpux;ury[i]=tmpuy;
                color[i]=color[j];
              }
           }
        }
        else if (lly[ti]>=lly[j]){
          if(urx[ti]>=urx[j]){
             if(ury[ti]>=ury[j]){
               urx[j]=llx[ti];
               i++;
               llx[i]=llx[ti];lly[i]=tmply;
               urx[i]=tmpux;ury[i]=lly[ti];
               color[i]=color[j];
             }
             else if(ury[ti]<=ury[j]){
               urx[j]=llx[ti];
               i++;
               llx[i]=llx[ti];lly[i]=ury[ti];
               urx[i]=tmpux;ury[i]=tmpuy;
               color[i]=color[j];
               i++;
               llx[i]=llx[ti];lly[i]=tmply;
               urx[i]=tmpux;ury[i]=lly[ti];
               color[i]=color[j];
             }
          }
          else if(urx[ti]<=urx[j]){
             if(ury[ti]>=ury[j]){
               llx[j]=urx[ti];
               i++;
               llx[i]=llx[ti];lly[i]=tmply;
               urx[i]=urx[ti];ury[i]=lly[ti];
               color[i]=color[j];
               i++;
               llx[i]=tmplx;lly[i]=tmply;
               urx[i]=llx[ti];ury[i]=tmpuy;
               color[i]=color[j];
             }
             else if(ury[ti]<=ury[j]){
               llx[j]=urx[ti];
               i++;
               llx[i]=tmplx;lly[i]=tmply;
               urx[i]=llx[ti];ury[i]=tmpuy;
               color[i]=color[j];
               i++;
               llx[i]=llx[ti];lly[i]=ury[ti];
               urx[i]=urx[ti];ury[i]=tmpuy;
               color[i]=color[j];               
               i++;
               llx[i]=llx[ti];lly[i]=tmply;
               urx[i]=urx[ti];ury[i]=lly[ti];
               color[i]=color[j];           
             }
          }
        }
     }
    }
     

int main(){
  FILE *in,*out;
  int a,b,n,tmp=0,k;
  in=fopen("rect1.in","r");
  out=fopen("rect1.out","w");
  fscanf(in,"%d %d %d",&a,&b,&n);
  for(i=1;i<2503;i++) area[i]=0;
  for(i=1;i<=n;i++){
    fscanf(in,"%d %d %d %d %d",&llx[i],&lly[i],&urx[i],&ury[i],&color[i]);
    ti=i;
    for(j=1;j<ti;j++)
      intersect();
  }
  for(j=1;j<=i;j++)
      area[color[j]]+=(urx[j]-llx[j])*(ury[j]-lly[j]);
  for(j=2;j<2503;j++)
     if(area[j]>0) 
        tmp+=area[j];
  area[1]=(a*b-tmp);
  for(j=1;j<2503;j++)
      if(area[j]>0)
        fprintf(out,"%d %d\n",j,area[j]);
  return 0;
}
if someone can help me I would appreciate a lot

wanderley2k
New poster
Posts: 28
Joined: Mon Mar 01, 2004 11:29 pm

Post by wanderley2k »

Try this. Take two shape and generate all Subshape. After test is a shape have other shape in it. If has other don

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:

Post by midra »

thanks!!!
But I already solve the problem..I think a big mistake is to NOT create a type for the rectangles, this can make really easy to debug and to understand the code
byee

Post Reply

Return to “Algorithms”