hdu 3265 Posters(线段树,扫描线)
程序员文章站
2022-07-13 11:03:13
...
题意:给你n张矩形海报,之后每张矩形之中又挖去一个小矩形,问你n个复合矩形的面积并
思路:我们把那个挖空的小矩形变换一下,变成4个矩形
就是这样,之后就变成了4个小矩形之后求一下面积并就好了
上代码吧:
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#define lson l, m , rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
const int maxn = 50000+10;
struct Seg
{
int r,l,h;
int f;
Seg(){};
Seg(double a,double b,double c,int d) : l(a),r(b),h(c),f(d){}
bool operator < (const Seg & cmp) const
{
return h < cmp.h;
}
}edg[maxn<<3];
int X[maxn<<3];
struct node
{
int len;
int cnt;
}ve[maxn<<2];
void pushdown(int l,int r,int rt)
{
if(ve[rt].cnt)
{
ve[rt].len = X[r+1] - X[l];
}
else if(l == r) ve[rt].len = 0;
else
{
ve[rt].len = ve[rt<<1].len + ve[rt<<1|1].len;
}
}
void update(int L,int R,int l,int r,int rt,int val)
{
// cout<<l<<" "<<r<<endl;
if(L>R) return ;
if(L<=l && R>=r)
{
ve[rt].cnt += val;
pushdown(l,r,rt);
return ;
}
int m = (r+l)>>1;
if(L<=m)
{
update(L,R,lson,val);
}
if(R>m)
{
update(L,R,rson,val);
}
pushdown(l,r,rt);
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int cnt = 0 ;
int a1,b1,c1,d1,a2,b2,c2,d2;
if(n == 0) break;
for(int i = 0 ; i < n ;i++)
{
scanf("%d%d%d%d%d%d%d%d",&a1,&b1,&c1,&d1,&a2,&b2,&c2,&d2);
X[cnt] = a1;
edg[cnt++] = Seg(a1,c1,b1,1);
X[cnt] = c1;
edg[cnt++] = Seg(a1,c1,b2,-1);
X[cnt] = a1;
edg[cnt++] = Seg(a1,c1,d2,1);
X[cnt] = c1;
edg[cnt++] = Seg(a1,c1,d1,-1);
X[cnt] = a1;
edg[cnt++] =Seg(a1,a2,b2,1);
X[cnt] = a2;
edg[cnt++] = Seg(a1,a2,d2,-1);
X[cnt] = c2;
edg[cnt++] = Seg(c2,c1,b2,1);
X[cnt] = c1;
edg[cnt++] = Seg(c2,c1,d2,-1);
}
sort(X,X+cnt);
sort(edg,edg+cnt);
int m = unique(X,X+cnt) - X;
long long ans = 0 ;
for(int i = 0 ; i < cnt ; i++)
{
int l = lower_bound(X,X+m,edg[i].l) - X;
int r = lower_bound(X,X+m,edg[i].r) - X -1;
update(l,r,0,m,1,edg[i].f);
ans += (long long)ve[1].len * (edg[i+1].h - edg[i].h);
}
printf("%lld\n",ans);
}
}