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!
終于做出來(lái)了，用隊(duì)列實(shí)現(xiàn)，沒(méi)接收一個(gè)就遍歷整個(gè)隊(duì)列。要注意的是要把隊(duì)列的大小用t記下，因?yàn)?/pre>
新加進(jìn)來(lái)的會(huì)改變隊(duì)列的大小。
用的是矩形分割：
原來(lái)的程序在分割與a相交的矩形b的時(shí)候，把a(bǔ)與b相交的部分也作為一個(gè)小矩形放在了后面。
這也就會(huì)多出很多，統(tǒng)計(jì)了一下對(duì)于最后一組測(cè)試數(shù)據(jù)有40多萬(wàn)個(gè)矩形，超時(shí)。
其實(shí)應(yīng)該把a(bǔ)整個(gè)放進(jìn)去，不該把a(bǔ)也分割的。
-
/*
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的下標(biāo)是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); }//如果不相交，放在隊(duì)列后面
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;
}