Sicily 1799. Slides

显然直接开个大数组模拟最简单，可是slide的坐标范围太大，但是slide的个数却不多, 用离散化的方法，先对坐标排序，然后重新标号。

/* source code of submission 339198, Zhongshan University Online Judge System */
#include<cstdio>
#include<memory.h>
#include<algorithm>
#include<map>
#include<set>

const int N=100;
using namespace std;
int slide[N][5];
int xl[N*2],yl[N*2];
int plane[N*2+3][N*2+3];
int n;

int main()
{
    while ( scanf("%d",&n), n!=0 )
    {
		//xs,ys分别保存x、y的所有坐标
        set<int> xs;
        set<int> ys;
        for (int i=0; i<n; ++i)
        {
            for (int j=0; j<5; ++j)
                scanf("%d",&slide[i][j]);
            
            xs.insert(slide[i][0]);
            xs.insert(slide[i][2]);

            ys.insert(slide[i][1]);
            ys.insert(slide[i][3]);
        }

        int xlen,ylen;//x和y的坐标数
        xlen=-1;
        for (set<int>::iterator it=xs.begin(); it!=xs.end(); ++it)
        {
            ++xlen;
            xl[xlen]=*it;//把集合xs中的x坐标放到数组xl中
        }
        
        ylen=-1;
        for (set<int>::iterator it=ys.begin(); it!=ys.end(); ++it)
        {
            ++ylen;
            yl[ylen]=*it;//把集合ys中的x坐标放到数组yl中
        }

		
        sort(xl,xl+xlen+1);
        sort(yl,yl+ylen+1);

		//建立映射xm[a]表示a坐标的新坐标
        map<int,int> xm;
        map<int,int> ym;

        for (int i=0; i<=xlen; ++i)
            xm[ xl[i] ]=i;

        for (int i=0; i<=ylen; ++i)
            ym[ yl[i] ]=i;

		//模拟填色
        memset( plane, 0, sizeof( plane) );
        for (int i=0; i<n; ++i)
        {
            for (int x=xm[ slide[i][0] ];  x<xm[ slide[i][2] ]; ++x)
            {
                for (int y=ym[ slide[i][1] ]; y<ym[ slide[i][3] ]; ++y)
                    plane[x][y]+=slide[i][4];
            }
        


        }
	
		//统计颜色数
        set<int> color;
        for (int i=0; i<xlen; ++i)
        {
          for (int  j=0; j<ylen; ++j)
            {
              color.insert(plane[i][j]);
            }
        }
        printf("%d/n",color.size()-1 );
    }
    return 0;
}