看到一坨矩形就要想到扫描线 (poj atantis)
我们把横边竖边分开计算, 因为横边竖边其实没有区别, 以下论述全为考虑竖边的
怎样统计一个竖边对答案的贡献呢? 答: 把这个竖边加入线段树, 当前的总覆盖长度 减去 加入前的总覆盖长度 的绝对值 即为这个竖边的贡献
这样做有一个要求, 横坐标相同的竖边, 要先加进去入边再删掉出边 (为什么呢? 考虑两个矩形, 一个矩形的右边和另一个矩形的左边的横坐标相同但上下错落)
- #include <algorithm>
- #include <iostream>
- #include <cstring>
- #include <cstdio>
- using namespace std;
- int n, qwq1, pwp1, qwq2, pwp2, cnt, m, num[20005], ans;
- struct Line{
- int uu, vv, ww, id;
- }li1[10005], li2[10005];
- bool cmp(Line x, Line y){
- if(x.uu!=y.uu) return x.uu<y.uu;
- else return x.id>y.id;
- }
- struct SGT{
- int sum[80005], len[80005];
- void update(int o, int l, int r, int x, int y, int k){
- if(num[l]>=x && num[r]<=y) sum[o] += k;
- else{
- int mid=(l+r)>>1;
- int lson=o<<1;
- int rson=lson|1;
- if(x<num[mid]) update(lson, l, mid, x, y, k);
- if(num[mid]<y) update(rson, mid, r, x, y, k);
- }
- if(sum[o]>0) len[o] = num[r] - num[l];
- else if(l+1==r) len[o] = 0;
- else len[o] = len[o<<1] + len[(o<<1)|1];
- }
- }sgt;
- int main(){
- cin>>n;
- for(int i=-10000; i<=10000; i++) num[++m] = i;
- for(int i=1; i<=n; i++){
- scanf("%d %d %d %d", &qwq1, &pwp1, &qwq2, &pwp2);
- cnt++;
- li1[cnt] = (Line){qwq1, pwp1, pwp2, 1};
- li2[cnt] = (Line){pwp1, qwq1, qwq2, 1};
- cnt++;
- li1[cnt] = (Line){qwq2, pwp1, pwp2, -1};
- li2[cnt] = (Line){pwp2, qwq1, qwq2, -1};
- }
- sort(li1+1, li1+1+cnt, cmp);
- sort(li2+1, li2+1+cnt, cmp);
- for(int i=1; i<=cnt; i++){
- int lst=sgt.len[1];
- sgt.update(1, 1, m, li1[i].vv, li1[i].ww, li1[i].id);
- ans += abs(sgt.len[1]-lst);
- }
- for(int i=1; i<=cnt; i++){
- int lst=sgt.len[1];
- sgt.update(1, 1, m, li2[i].vv, li2[i].ww, li2[i].id);
- ans += abs(sgt.len[1]-lst);
- }
- cout<<ans<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2514445.html