USACO chapter 3 section 1 Shaping Regions

USER: tian tianbing [tbbd4261]
TASK: rect1
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 3024 KB]
   Test 2: TEST OK [0.000 secs, 3024 KB]
   Test 3: TEST OK [0.011 secs, 3024 KB]
   Test 4: TEST OK [0.000 secs, 3024 KB]
   Test 5: TEST OK [0.000 secs, 3024 KB]
   Test 6: TEST OK [0.000 secs, 3024 KB]
   Test 7: TEST OK [0.022 secs, 3024 KB]
   Test 8: TEST OK [0.011 secs, 3024 KB]
   Test 9: TEST OK [0.022 secs, 3024 KB]
   Test 10: TEST OK [0.022 secs, 3024 KB]
   Test 11: TEST OK [0.022 secs, 3024 KB]

All tests OK.
Your program ('rect1') produced all correct answers!  This is your
submission #15 for this problem.  Congratulations!
 
     终于做出来了,用队列实现,没接收一个就遍历整个队列。要注意的是要把队列的大小用t记下,因为
新加进来的会改变队列的大小。
    用的是矩形分割:
原来的程序在分割与a相交的矩形b的时候,把a与b相交的部分也作为一个小矩形放在了后面。
这也就会多出很多,统计了一下对于最后一组测试数据有40多万个矩形,超时。
其实应该把a整个放进去,不该把a也分割的。



 

/*
ID:tbbd4261
PROG:rect1
LANG:C++
*/

#include
<fstream>
#include
<queue>
#include
<string.h>
using namespace std;
ifstream fin(
"rect1.in");
ofstream fout(
"rect1.out");
struct type
{
       
int x1,y1,x2,y2,color;
};

int w,h,n,i,cnt;
int color[2505]={0};
queue
<type>Q;
inline 
int max(int a, int b){ return a>b?a:b; }
inline 
int min(int a, int b){ return a>b?b:a; } 
bool isIn(type &a, type &b)//判断是否相交 
{
    
if(a.x1>=b.x2)return false;
    
if(a.x2<=b.x1)return false;
    
if(a.y1>=b.y2)return false;
    
if(a.y2<=b.y1)return false;
    
return true;
}

void add(int x1, int y1, int x2, int y2, int c)
{
      type t; t.x1
=x1; t.y1=y1; t.x2=x2; t.y2=y2; t.color=c; 
      color[c]
+=(x2-x1)*(y2-y1);
      Q.push(t);
}

 
void dec()
{
       type t
=Q.front(); Q.pop();
       color[t.color]
-=(t.x2-t.x1)*(t.y2-t.y1);
}

 
void deal(type &a, type &b) //a与b交,b的下标是j                 
 {     
     
if(a.x1>b.x1&&a.x1<b.x2) add(b.x1, b.y1,a.x1,b.y2,b.color);//S1
     if(a.x2>b.x1&&a.x2<b.x2) add(a.x2,b.y1, b.x2, b.y2,b.color); //S3
     if(a.y1>b.y1&&a.y1<b.y2) add(max(a.x1,b.x1),b.y1,min(a.x2,b.x2),a.y1,b.color);//S2
     if(a.y2>b.y1&&a.y2<b.y2) add(max(a.x1,b.x1),a.y2,min(a.x2,b.x2),b.y2,b.color);//S4
     
//add(max(a.x1,b.x1),max(a.y1,b.y1),min(a.x2,b.x2),min(a.y2,b.y2),a.color);//a与b相交的部分 
     dec();
 }

int main()
{
    memset(color,
0,sizeof color);
    fin
>>w>>h>>n;
    color[
1]=w*h;
    type temp;  
    temp.x1
=0; temp.y1=0; temp.x2=w; temp.y2=h; temp.color=1;
    Q.push(temp);
    
for(i=1; i<=n; i++)
    {
             fin
>>temp.x1>>temp.y1>>temp.x2>>temp.y2>>temp.color;
             
for(int t=Q.size(),j=1;j<=t; j++ )
                     
if(isIn(temp,Q.front() ))
                          deal( temp,Q.front() );
                     
else { type t=Q.front(); Q.pop();Q.push(t); }//如果不相交,放在队列后面
        add(temp.x1,temp.y1,temp.x2,temp.y2,temp.color);
    }
    
for(i=1; i<=2500; i++)
              
if(color[i]) fout<<i<<' '<<color[i]<<endl;  
              
    
return 0;
}

 

posted on 2010-08-04 16:51 田兵 阅读(60) 评论(0)  编辑 收藏 引用 所属分类: USACO


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜