Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
带注释,详细代码// Atlantis #include <iostream> #include <iomanip> #include <algorithm> #define pb push_back #define lc (p*2) #define rc (p*2+1) #define rep(i, s, t) for(int i=s; i<=t; i++) #define F first #define S second #define all(x) x.begin(), x.end() #define debug(x) cout<<#x<<":"<<x<<endl; #define int long long const int SIZE=3000010; using namespace std; int n; struct eachedge { double x, y1, y2, k; } e[SIZE]; bool cmp(eachedge a, eachedge b) { if(a.x!=b.x) return a.x<b.x; return a.k>b.k; } double rk[SIZE]; double raw[SIZE]; int cnt=0; struct segmentTreeNode { int l, r, cnt; double len; // cnt: 被多少个矩形完整地包含 } t[SIZE]; void pushup(int p) { if(!t[p].l && !t[p].r) return; // 无用的节点 if(t[p].cnt) t[p].len=raw[t[p].r+1]-raw[t[p].l]; else t[p].len=t[lc].len+t[rc].len; } void build(int p, int l, int r) { t[p].l=l; t[p].r=r; if(l==r) return; int mid=(l+r)/2; build(lc, l, mid); build(rc, mid+1, r); } void change(int p, int l, int r, int v) { if(l<=t[p].l && t[p].r<=r) { t[p].cnt+=v; pushup(p); return; } int mid=(t[p].l+t[p].r)/2; if(l<=mid) change(lc, l, r, v); if(r>mid) change(rc, l, r, v); pushup(p); } signed main() { int tot=1; while(cin>>n && n) { cnt=0; rep(i, 1, n) { double x1, y1, x2, y2; cin>>x1>>y1>>x2>>y2; // 存储抽象矩形的每一条纵边 e[i*2-1].x=x1, e[i*2-1].y1=y1, e[i*2-1].y2=y2; e[i*2].x=x2, e[i*2].y1=y1, e[i*2].y2=y2; e[i*2-1].k=1, e[i*2].k=-1; // 预处理离散化 rk[++cnt]=y1, rk[++cnt]=y2; } sort(rk+1, rk+cnt+1); cnt=unique(rk+1, rk+cnt+1)-rk-1; // 处理离散化后的索引 raw rep(i, 1, n*2) { int p1=lower_bound(rk+1, rk+cnt+1, e[i].y1)-rk; int p2=lower_bound(rk+1, rk+cnt+1, e[i].y2)-rk; raw[p1]=e[i].y1; raw[p2]=e[i].y2; e[i].y1=p1; e[i].y2=p2; } // 将所有边按照 x 坐标排序并初始化线段树 sort(e+1, e+n*2+1, cmp); build(1, 1, n*2); // 开始扫描线算法 double ans=0; rep(i, 1, n*2) { // 计算当前边对总面积的贡献 change(1, e[i].y1, e[i].y2-1, e[i].k); ans+=t[1].len*(e[i+1].x-e[i].x); } cout<<"Test case #"<<tot++<<endl; cout<<"Total explored area: "<<fixed<<setprecision(2)<<ans<<endl<<endl; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator