2017 ACM-ICPC 亚洲区（南宁赛区）网络赛 Overlapping Rectangles 矩形并面积和

Overlapping Rectangles

题意：求 n 个矩形并面积和

tags：扫描线+线段树，模板题

参考博客

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define rep(i,a,b) for (int i=a; i<=b; ++i)
#define per(i,b,a) for (int i=b; i>=a; --i)
#define mes(a,b)
memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define MP make_pair
#define PB push_back
#define fi
first
#define se
second
typedef long long ll;
const int N=1000+5;
int col[N<<3], cnt, res;
double X[N<<3], Sum[N<<3], Sum2[N<<3];
//多开一倍，因为 x坐标有两个
struct Seg {
double l, r, h;
int flag;
Seg(){}
Seg(double l,double r,double h,int flag):l(l),r(r),h(h),flag(flag){}
bool operator <(const Seg & object ) const{
return h < object.h;
}
}S[N<<2];
void pushup(int ro, int l, int r)
{
if(col[ro])
//覆盖一次
Sum[ro]=X[r+1]-X[l];
else if(l==r) Sum[ro]=0;
else Sum[ro]=Sum[ro<<1]+Sum[ro<<1|1];
if(col[ro]>=2) // 覆盖两次以上
Sum2[ro]=X[r+1]-X[l];
else if(l==r) Sum2[ro]=0;
else if(col[ro]==1) Sum2[ro]=Sum[ro<<1] +Sum[ro<<1|1];
else if(col[ro]==0) Sum2[ro]=Sum2[ro<<1] +Sum2[ro<<1|1];
}
void update(int L, int R, int c, int ro, int l, int r)
// [l,r]当前区间，[L,R]目标区间
{
if(L<=l && r<=R)
{
col[ro] += c;
pushup(ro, l, r);
return ;
}
int mid = (l+r)>>1;
if(L<=mid) update(L, R, c, ro<<1, l, mid);
if(R>mid) update(L, R, c, ro<<1|1, mid+1, r);
pushup(ro, l, r);
}
int binary_find(double x)
{
int l=1, r=res, ans, mid;
while(l<=r)
{
mid = (l+r)>>1;
if(X[mid] >= x) ans=mid, r=mid-1;
else l=mid+1;
}
return ans;
}
double solve(int n)
{
cnt = res = 0;
for(int i=1; i<=n; ++i)
{
double x1, y1, x2, y2;
scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
S[++cnt]=Seg(x1,x2,y1,1);
X[cnt]=x1;
S[++cnt]=Seg(x1,x2,y2,-1);
X[cnt]=x2;
}
sort(X+1, X+1+cnt);
sort(S+1, S+1+cnt);
++res;
for(int i=2; i<=cnt; ++i) {
// 去重，x坐标过大的话，就离散化
if(X[i]!=X[i-1])
X[++res]=X[i];
}
memset(Sum, 0, sizeof(Sum));
memset(col, 0, sizeof(col));
memset(Sum2, 0, sizeof(Sum2));
double ans=0;
for(int i=1; i<cnt; ++i)
{
int l = binary_find(S[i].l);
//二分左端点
int r = binary_find(S[i].r)-1;
// 左闭右开,二分右端点
update(l, r, S[i].flag, 1, 1, res);
ans += Sum[1]*(S[i+1].h-S[i].h);
//矩阵并
//ans += Sum2[1]*(S[i+1].h-S[i].h); //矩阵交集

}
return ans;
}
int main()
{
int n;
while(scanf("%d", &n), n)
{
printf("%.0fn", solve(n));
}
puts("*");
return 0;
}