首页 > 代码库 > hdu1828(线段树+扫描线)
hdu1828(线段树+扫描线)
又知道了线段树的一种用法,除了单点更新,区间更新,还有这种在一段线段上标号但不往下推。 真是神奇
hdu1828
#include <iostream>#include <stdio.h>#include <string.h>#include <math.h>#include <algorithm>#include <string>#include <queue>#include <map>#include <stdlib.h>using namespace std;#define N 5050struct RECT{ int x1,y1,x2,y2;}g[N];struct LINE{ int k,b,d; int flag;}line[4*N];int ans=0;int n;int l[200000],r[200000],mark[200000],yb[200000],yd[200000],num[200000];int cmp(LINE x,LINE y){ return x.k<y.k;}void build(int tl,int tr,int s){ l[s]=tl; r[s]=tr; mark[s]=0;yb[s]=0; yd[s]=0; num[s]=0; if(tl==tr) return ; int mid=(tl+tr)/2; build(tl,mid,2*s); build(mid+1,tr,2*s+1);}void up(int s){ if(mark[s]>0) { num[s]=1; yb[s]=1; yd[s]=1; } else { if(l[s]==r[s]) { num[s]=0; yb[s]=0; yd[s]=0; } else { if(yd[2*s]==1&&yb[2*s+1]==1) num[s]=num[2*s]+num[2*s+1]-1; else num[s]=num[2*s]+num[2*s+1]; yb[s]=yb[2*s]; yd[s]=yd[2*s+1]; } }}void update(int tl,int tr,int sign,int s){ if(tl==l[s]&&tr==r[s]) { mark[s]+=sign; up(s); return ; } int mid=(l[s]+r[s])/2; if(tr<=mid) update(tl,tr,sign,2*s); else if(tl>mid) update(tl,tr,sign,2*s+1); else { update(tl,mid,sign,2*s); update(mid+1,tr,sign,2*s+1); } up(s);}void fuc(){ int cnt=0; int mix=200000000,mxx=-200000000; for(int i=0;i<n;i++) { line[cnt].k=g[i].y1; line[cnt].b=g[i].x1; line[cnt].d=g[i].x2-1;//注意可能为负的 line[cnt].flag=1; cnt++; mix=min(mix,g[i].x1); mxx=max(mxx,g[i].x2-1); line[cnt].k=g[i].y2; line[cnt].b=g[i].x1; line[cnt].d=g[i].x2-1; line[cnt].flag=-1; cnt++; } sort(line,line+cnt,cmp); build(mix,mxx,1); for(int i=0;i<cnt-1;i++) { update(line[i].b,line[i].d,line[i].flag,1); ans += (line[i+1].k-line[i].k)*2*num[1]; }}int main(){ while(scanf("%d",&n)!=EOF) { for(int i=0;i<n;i++) { scanf("%d%d%d%d",&g[i].x1,&g[i].y1,&g[i].x2,&g[i].y2); g[i].x1+=10011; g[i].x2+=10011; g[i].y1+=10011; g[i].y2+=10011; } if(n==0) { printf("0\n"); continue; } ans=0; fuc(); // for(int i=0;i<n;i++) { swap(g[i].x1,g[i].y1); swap(g[i].x2,g[i].y2); } fuc(); printf("%d\n",ans); } return 0;}
hdu1828(线段树+扫描线)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。