# 加载中...

• 博客等级：
• 博客积分：0
• 博客访问：35,674
• 关注人气：17
• 获赠金笔：0支
• 赠出金笔：0支
• 荣誉徽章：

## hdu 4419 (Colourful Rectangle) 扫描线求多面积并  杭州网赛1010

(2012-09-23 18:10:08)

### 杂谈

1W个点    暴力的开了7个线段树    分别求r b g rg rb bg rbg  的面积

#include <iostream>
#include <string>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <stack>
#include <list>
#include <algorithm>

using namespace std;

#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define maxs 100100

const unsigned short pattern[8] = {0x0000,0x0001,0x0002,0x0004,0x0003,0x0006,0x0005,0x0007};
//r = 1 , b = 2 , g = 3  , rb = 4 , bg = 5 , rg = 6 , rgb = 7

struct seg_tree
{
int left , right , high , kinds;
int edge;
seg_tree(){}
seg_tree(int x1 , int x2 , int y , int e , int ki) : left(x1),right(x2),high(y),edge(e),kinds(ki){}    //设置默认付值语句  都忘了   完全把VC++还给华姐了
bool operator < (const seg_tree &cmp) const
{
return high < cmp.high;
}
}st[maxs<<2];
int cnt[maxs<<2];   //   表示该区间下边比上边多几个    当一条边在某个区间时 , 这个区间的cnt就+edge    upedge 为1  downedge 为-1
int kid[maxs<<2];   // 神马颜色
int len[maxs<<2];   //   区间的边长
int ds[maxs<<2];    //离散(dispersion)

int Bsearch(int key , int right)
{
int l = 0 , r = right - 1;
while(l <= r)
{
int mid = (l + r)>>1;
if(key == ds[mid])return mid;
if(key > ds[mid]) l = mid+1;
else r = mid-1;
}
return -1;
}

void dye(int xs, int xe , int idx)
{
if(cnt[idx]) len[idx] = ds[xe+1] - ds[xs];
else if(xs == xe) len[idx] = 0;
else len[idx] = len[LL(idx)] + len[RR(idx)];
}

void update(int xs , int xe ,int op , int left ,int right, int idx)
{
if(xs <= left && xe >= right)
{
cnt[idx] += op;
dye(left ,right , idx);
return;
}
int mid = (right + left)>>1;

if(xs <= mid) update(xs , xe , op , left , mid , LL(idx));
if(mid < xe) update(xs , xe , op , mid+1 , right ,RR(idx));
dye(left , right , idx);
}

int main()
{
int t;
int kkk = 0;
scanf("%d",&kkk);
int num = 1;
while(kkk--)
{
scanf("%d",&t);
int edge;
int m = 0;
for(int i = 0 ; i < t ; ++i)
{
char yanshe ;
int tempy = 0;
cin>>yanshe;
if(yanshe == 'R')//r = 1 , b = 2 , g = 3  , rb = 4 , bg = 5 , rg = 6 , rgb = 7
tempy = pattern[1];
else if(yanshe == 'G')
tempy = pattern[3];
else tempy = pattern[2];
int x1 , y1 , x2 , y2;
//scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
cin>>x1>>y1>>x2>>y2;   //left-bottom's coordinate and the right-top's coordinate of a rectangle
st[m] = seg_tree(x1 , x2 , y2 ,1,tempy);
ds[m++] = x1;
st[m] = seg_tree(x1 , x2 , y1 ,-1,tempy);
ds[m++] = x2;
}
sort(st,st+m);
sort(ds,ds+m);
int temp = 1;
for(int i = 1 ; i < m ; ++i)
if(ds[i] != ds[i-1]) ds[temp++] = ds[i];
memset(cnt , 0 , sizeof(cnt));
memset(len , 0 , sizeof(len));
__int64 ansr = 0 , ansb = 0 , ansg = 0 , ansrg = 0 , ansrb = 0 , ansgb = 0 , ansrgb = 0 ;
//area
for(int i = 0 ; i < m-1; ++i)//r
{
if(st[i].kinds & pattern[1])
{
int tmph = 0;
for(int j = i+1 ; j < m; ++j)//next hig
{
if(st[j].kinds & pattern[1])
{
tmph = st[j].high;
break;
}
}
int left  = Bsearch(st[i].left , temp);
int right = Bsearch(st[i].right, temp)-1;
//cout<<"temph= "<<tmph <<endl;
if(left <= right)update(left , right , st[i].edge , 0 , temp-1 , 1);
//cout<<" len = "<<len[1]<<" high "<<tmph - st[i].high<<endl;
ansr += ((__int64)len[1])*(tmph - st[i].high);
}
}
//cout<<ansr<<endl;
memset(cnt , 0 , sizeof(cnt));
memset(len , 0 , sizeof(len));
for(int i = 0 ; i < m-1; ++i)//b
{
if(st[i].kinds & pattern[2])
{
int tmph = 0;
for(int j = i+1 ; j < m; ++j)//next hig
{
if(st[j].kinds & pattern[2])
{
tmph = st[j].high;
break;
}
}
int left  = Bsearch(st[i].left , temp);
int right = Bsearch(st[i].right, temp)-1;
if(left <= right)update(left , right , st[i].edge , 0 , temp-1 , 1);
ansb += ((__int64)len[1])*(tmph - st[i].high);
}
}
memset(cnt , 0 , sizeof(cnt));
memset(len , 0 , sizeof(len));
for(int i = 0 ; i < m-1; ++i)//g
{
if(st[i].kinds & pattern[3])
{
int tmph = 0;
for(int j = i+1 ; j < m; ++j)//next hig
{
if(st[j].kinds & pattern[3])
{
tmph = st[j].high;
break;
}
}
int left  = Bsearch(st[i].left , temp);
int right = Bsearch(st[i].right, temp)-1;
if(left <= right)update(left , right , st[i].edge , 0 , temp-1 , 1);
ansg += ((__int64)len[1])*(tmph - st[i].high);
}
}
memset(cnt , 0 , sizeof(cnt));
memset(len , 0 , sizeof(len));
for(int i = 0 ; i < m-1; ++i)//rg
{
if((st[i].kinds & pattern[3])||(st[i].kinds & pattern[1]))
{
//cout<<"l = "<<st[i].left<<"r = "<<st[i].right<<endl;
int tmph = 0;
for(int j = i+1 ; j < m; ++j)//next hig
{
if((st[j].kinds & pattern[3])||(st[j].kinds & pattern[1]))
{
tmph = st[j].high;
break;
}
}
//cout<<"tph = "<<tmph<<endl;
//cout<<"h = "<<st[i].high<<endl;
int left  = Bsearch(st[i].left , temp);
int right = Bsearch(st[i].right, temp)-1;
if(left <= right)update(left , right , st[i].edge , 0 , temp-1 , 1);
//cout<<" len = "<<len[1]<<" high "<<tmph - st[i].high<<endl;
ansrg += ((__int64)len[1])*(tmph - st[i].high);
}
}
//cout<<"   "<<ansrg<<endl;
memset(cnt , 0 , sizeof(cnt));
memset(len , 0 , sizeof(len));
for(int i = 0 ; i < m-1; ++i)//bg
{
if((st[i].kinds & pattern[2])||(st[i].kinds & pattern[3]))
{
int tmph = 0;
for(int j = i+1 ; j < m; ++j)//next hig
{
if((st[j].kinds & pattern[2])||(st[j].kinds & pattern[3]))
{
tmph = st[j].high;
break;
}
}
int left  = Bsearch(st[i].left , temp);
int right = Bsearch(st[i].right, temp)-1;
if(left <= right)update(left , right , st[i].edge , 0 , temp-1 , 1);
ansgb += ((__int64)len[1])*(tmph - st[i].high);
}
}
memset(cnt , 0 , sizeof(cnt));
memset(len , 0 , sizeof(len));
for(int i = 0 ; i < m-1; ++i)//rb
{
if((st[i].kinds & pattern[2])||(st[i].kinds & pattern[1]))
{
int tmph = 0;
for(int j = i+1 ; j < m; ++j)//next hig
{
if((st[j].kinds & pattern[2])||(st[j].kinds & pattern[1]))
{
tmph = st[j].high;
break;
}
}
int left  = Bsearch(st[i].left , temp);
int right = Bsearch(st[i].right, temp)-1;
if(left <= right)update(left , right , st[i].edge , 0 , temp-1 , 1);
ansrb += ((__int64)len[1])*(tmph - st[i].high);
}
}
memset(cnt , 0 , sizeof(cnt));
memset(len , 0 , sizeof(len));
for(int i = 0 ; i < m-1; ++i)//rb
{
if((st[i].kinds & pattern[2])||(st[i].kinds & pattern[3])||(st[i].kinds & pattern[1]))
{
int tmph = 0;
for(int j = i+1 ; j < m; ++j)//next hig
{
if((st[j].kinds & pattern[2])||(st[j].kinds & pattern[3])||(st[j].kinds & pattern[1]))
{
tmph = st[j].high;
break;
}
}
int left  = Bsearch(st[i].left , temp);
int right = Bsearch(st[i].right, temp)-1;
if(left <= right)update(left , right , st[i].edge , 0 , temp-1 , 1);
ansrgb +=((__int64)len[1])*(tmph - st[i].high);
}
}
__int64 sr_g,sr_b,sb_g;
sr_g=ansr+ansg-ansrg;
sr_b=ansr+ansb-ansrb;
sb_g=ansb+ansg-ansgb;
__int64 ar,ag,ab,arg,arb,arbg,abg;
arbg=ansrgb-ansr-ansg-ansb+sr_g+sr_b+sb_g;
arg=sr_g-arbg;
arb=sr_b-arbg;
abg=sb_g-arbg;
ar=ansr-arg-arb-arbg;
ab=ansb-abg-arb-arbg;
ag=ansg-arg-abg-arbg;
printf("Case %d:\n",num++);
printf("%I64d\n%I64d\n%I64d\n%I64d\n%I64d\n%I64d\n%I64d\n",ar,ag,ab,arg,arb,abg,arbg);
//printf("Test case #%d\nTotal explored area: %.2lf\n\n",num++ ,ans);
}
return 0;
}

0

• 评论加载中，请稍候...

发评论

以上网友发言只代表其个人观点，不代表新浪网的观点或立场。

新浪BLOG意见反馈留言板　电话：4000520066 提示音后按1键（按当地市话标准计费）　欢迎批评指正

新浪公司 版权所有