扫描线 模板

2019-04-14 21:12发布

站内文章 / 模拟电子
12444 0 1063
测试题目：HDU 1542 using namespace std; const int maxn = 100 + 5; const int TOT_SEG = maxn * 2; /** Seg ** l,r,h 分别为线段的左端点，右端点，高 ** f 标识上下边 */ struct Seg{ int f; double l,r,h; void set(double ll,double rr,double hh,int d){ l = ll,r = rr,h = hh,f = d; } }Segs[TOT_SEG]; bool cmp(const Seg& a,const Seg& b){ return a.h < b.h; } double AR[TOT_SEG]; /** 区间长度 */ map<double,int> POS; /** 将端点 HASH 到区间上 */ int Seg_CNT,HASH_SEG_CNT; void SEG_HASH(){ POS.clear();HASH_SEG_CNT = 2; sort(Segs + 1,Segs + Seg_CNT,cmp); sort(AR + 1,AR + Seg_CNT); for(int i = 2;i < Seg_CNT;++i){ if(AR[i] != AR[i - 1]){ AR[HASH_SEG_CNT] = AR[i]; POS[AR[i]] = HASH_SEG_CNT++; } } for(int i = 1;i < HASH_SEG_CNT;++i){ AR[i] = AR[i + 1] - AR[i]; } } HDU 1542 代码： #include #define sf scanf #define pf printf using namespace std; const int maxn = 100 + 5; const int TOT_SEG = maxn * 2; /** Seg ** l,r,h 分别为线段的左端点，右端点，高 ** f 标识上下边 */ struct Seg{ int f; double l,r,h; void set(double ll,double rr,double hh,int d){ l = ll,r = rr,h = hh,f = d; } }Segs[TOT_SEG]; bool cmp(const Seg& a,const Seg& b){ return a.h < b.h; } double AR[TOT_SEG]; /** 区间长度 */ map<double,int> POS; /** 将端点 HASH 到区间上 */ int Seg_CNT,HASH_SEG_CNT; void SEG_HASH(){ POS.clear();HASH_SEG_CNT = 2; sort(Segs + 1,Segs + Seg_CNT,cmp); sort(AR + 1,AR + Seg_CNT); for(int i = 2;i < Seg_CNT;++i){ if(AR[i] != AR[i - 1]){ AR[HASH_SEG_CNT] = AR[i]; POS[AR[i]] = HASH_SEG_CNT++; } } for(int i = 1;i < HASH_SEG_CNT;++i){ AR[i] = AR[i + 1] - AR[i]; } } int FALG[TOT_SEG]; /** SEG_TREE */ #define lson rt << 1 , l , mid #define rson rt << 1 | 1,mid + 1,r double _SUM[TOT_SEG << 2]; void PushUp(int rt){ _SUM[rt] = _SUM[rt << 1] + _SUM[rt << 1 | 1]; } void Build(int rt,int l,int r){ if(l == r){ _SUM[rt] = FALG[l] = 0; return; } int mid = l + r >> 1; Build(lson),Build(rson); } void Update(int rt,int l,int r,int L,int R,int d){ if(l == r){ FALG[l] += d; if(FALG[l] == 0) _SUM[rt] = 0; else _SUM[rt] = AR[r]; return; } int mid = l + r >> 1; if(L <= mid) Update(lson,L,R,d); if(R > mid) Update(rson,L,R,d); PushUp(rt); } int main(){ int n,ca = 0; while( ~sf("%d",&n) && n ){ int tmp = 1;double x1,x2,y1,y2; for(int i = 0;i < n;++i){ sf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2); Segs[tmp].set(x1,x2,y1,1); AR[tmp++] = x1; Segs[tmp].set(x1,x2,y2,-1); AR[tmp++] = x2; } // POS.clear(); // sort(Segs + 1,Segs + tmp,cmp); // sort(AR + 1,AR + tmp); // AR[tmp] = -1; // // // /** 点去重 + 点HASH*/ // int AR_TMP = 2; // for(int i = 2;i < tmp;++i) // if(AR[i] != AR[i - 1]){ // AR[AR_TMP] = AR[i]; // POS[AR[i]] = AR_TMP++; // } // // /** 点变为区间 */ // for(int i = 1;i < AR_TMP;++i){ // AR[i] = AR[i + 1] - AR[i]; // } Seg_CNT = tmp; SEG_HASH(); int AR_TMP = HASH_SEG_CNT; Build(1,1,AR_TMP - 2); double ans = 0; for(int i = 1;i < tmp;++i){ int L = POS[Segs[i].l],R = POS[Segs[i].r] - 1; Update(1,1,AR_TMP - 2,L,R,Segs[i].f); ans = ans + _SUM[1] * (Segs[i + 1].h - Segs[i].h); } pf("Test case #%d ",++ca); pf("Total explored area: %.2lf ",ans); } }

热门文章