poj 3695 Rectangles 线段树扫描线 or 容斥原理

59 阅读 0 评论 39 点赞

我是靠谱客的博主端庄招牌，最近开发中收集的这篇文章主要介绍poj 3695 Rectangles 线段树扫描线 or 容斥原理，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

POJ 3695

题意 : 求矩形的面积并

扫描线：直接线段树扫描线会超时，因为询问实在是太多了，必须要离散化，离散化如果还超时的话只能继续各种优化了，
这里我把x边都预处理一下，就避免了询问里再排序

容斥原理：对于每一次询问处理出重合 1 到 r 次的面积(r 为每次询问的矩形数) ，然后进行容斥原理，这里我处理重合面积的方法是这样的，
对于前两个矩形如果重合，就构造个重合部分的矩形继续往下搜

线段树

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
struct REC{
int x1,y1,x2,y2;
}rec[22];
struct seg{
int x1,x2,y,h,flag,id;
seg(){}
seg(int x1,int x2,int h,int flag,int id) : x1(x1), x2(x2), h(h), flag(flag), id(id) {}
bool operator < (const seg &a) const {
return h<a.h;
}
}ss[55];
struct PP{
int x,id;
bool operator < (const PP &a) const
{
return x<a.x;
}
}ax[55];
int sum[11111],cnt[11111],xx[111],vis[22];
void push_up(int rt,int l,int r)
{
if(cnt[rt])
sum[rt] = xx[r+1]-xx[l];
else if(l==r)
sum[rt] = 0;
else
sum[rt] = sum[rt<<1]+sum[rt<<1|1];
}
void update(int rt,int l,int r,int L,int R,int flag)
{
if( L<=l && R>=r)
{
cnt[rt]+=flag;
push_up(rt,l,r);
return ;
}
int mid = (l+r)>>1;
if(L<=mid)
update(lson,L,R,flag);
if(R>mid)
update(rson,L,R,flag);
push_up(rt,l,r);
}
int bin(int x,int l,int r)
{
while(l<=r)
{
int mid = (l+r)>>1;
if(xx[mid] == x)
return mid;
if(xx[mid] > x)
r = mid-1;
else
l = mid+1;
}
}
void init()
{
memset(cnt,0,sizeof(cnt));
memset(sum,0,sizeof(sum));
}
int main()
{
int n,m,i,x,r,j;
int cas = 1;
while(scanf("%d%d", &n, &m)!=-1 && n)
{
printf("Case %d:n", cas++);
int d = 0;
for(i = 1;i <= n ; i++)
{
scanf("%d%d%d%d", &rec[i].x1,&rec[i].y1,&rec[i].x2,&rec[i].y2);
ax[d].x = rec[i].x1;
ax[d].id = i;
ss[d++] = seg(rec[i].x1,rec[i].x2,rec[i].y1,1,i);
ax[d].x = rec[i].x2;
ax[d].id = i;
ss[d++] = seg(rec[i].x1,rec[i].x2,rec[i].y2,-1,i);
}
sort(ss,ss+d);
sort(ax,ax+d);
int dd = 1;
for(i = 1;i < d; i++)
if(ax[i].x!=ax[i-1].x)
ax[dd++] = ax[i];
for(i = 1;i <= m ;i++)
{
for(j = 1;j <= n; j++)
vis[j] = 0;
scanf("%d", &r);
int mm = 0;
while(r--)
{
scanf("%d", &x);
vis[x]++;
}
int k = 0;
for(j = 0;j < dd; j++)
{
if(!vis[ax[j].id])
continue;
xx[k++] = ax[j].x;
}
int ans = 0;
int pre = 0;
int preh = -1;
for(j = 0;j < d; j++)
{
if(!vis[ss[j].id])
continue;
int l = bin(ss[j].x1,0,k-1);
int r = bin(ss[j].x2,0,k-1)-1;
update(1,0,k-1,l,r,ss[j].flag);
//	printf("sum[1] = %dn",sum[1]);
if(preh>=0)
ans += pre*(ss[j].h-preh);
preh = ss[j].h;
pre = sum[1];
}
printf("Query %d: %dn",i,ans);
}
puts("");
}
return 0;
}

容斥原理

#include <stdio.h>
#include <string.h>
#include <algorithm>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a>b?b:a)
using namespace std;
struct REC{
int x1,x2,y1,y2;
}rec[22],cur[22],d[22];
int change[22] , top;
void find(int now,int num,int tot)
{
int i;
if(num == tot)
{
if(tot==1)
{
change[tot] += (d[0].x2-d[0].x1)*(d[0].y2-d[0].y1);
find(now,num,tot+1);
return ;
}
int mx1 = max(d[tot-1].x1,d[tot-2].x1);
int mx2 = min(d[tot-1].x2,d[tot-2].x2);
int my1 = max(d[tot-1].y1,d[tot-2].y1);
int my2 = min(d[tot-1].y2,d[tot-2].y2);
if(mx1 < mx2 && my1 < my2)
{
d[tot-1].x1 = mx1;
d[tot-1].x2 = mx2;
d[tot-1].y1 = my1;
d[tot-1].y2 = my2;
change[tot] += (mx2-mx1)*(my2-my1);
//	printf("tot = %dn", tot);
//	printf("%d %d %d %dn",mx1,my1,mx2,my2);
find(now,num,tot+1);
}
}
else
for(i = now;i < top; i++)
{
d[num] = cur[i];
find(i+1,num+1,tot);
}
}
int main()
{
int n,m,i,j,r,x;
int cas = 1;
while(scanf("%d%d", &n , &m )!=-1 && n)
{
printf("Case %d:n", cas++);
for(i = 1;i <= n; i ++)
scanf("%d%d%d%d", &rec[i].x1, &rec[i].y1, &rec[i].x2, &rec[i].y2);
for(i = 1;i <= m; i++)
{
scanf("%d", &r);
for(j = 0;j < r; j++)
{
scanf("%d", &x);
cur[j] = rec[x];
}
top = r;
for(j = 1;j <= r; j++)
change[j] = 0;
find(0,0,1);
int ans = 0;
for(j = 1;j <= r; j++)
{
//	printf("change[%d] = %dn",j , change[j]);
if(j&1)
ans += change[j];
else
ans -= change[j];
}
printf("Query %d: %dn",i, ans);
}
puts("");
}
return 0;
}