STL

结构体+优先队列

数据结构

图论

数论

DP

几何

扫描线

//求的是区域的面积 double a[4*N]; double tree[N*4]; int lazy[N*4]; struct node{ double l,r,h; int f; node(){} node(double l,double r,double h,int f):l(l),r(r),h(h),f(f){} bool operator< (const node &a)const { return h < a.h;//按照h从小到达排序 } }b[4*N]; void pushup(int rt,int left,int right){ if(lazy[rt]) tree[rt] = a[right+1]-a[left];//下面的区间都有用 else if(left == right) tree[rt] = 0;//如果到了子节点，则说明没用了 else tree[rt] = tree[2*rt]+tree[2*rt+1];//下面的区间可能还有作用 } void update(int rt,int left,int right,int l,int r,int c){ if(left >= l && right <= r){ lazy[rt] += c; pushup(rt,left,right); return; } int mid = (left+right)/2; if(l <= mid) update(2*rt,left,mid,l,r,c); if(r > mid) update(2*rt+1,mid+1,right,l,r,c); pushup(rt,left,right); } void solve(int n,int flag){ memset(tree,0,sizeof tree);//维护的是横坐标的值 memset(lazy,0,sizeof lazy);//标记这片区域是否还有点 int cnt = 0; for(int i = 1;i <= n;i++){ double x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2; a[++cnt] = x1; b[cnt] = node(x1,x2,y1,1);//第一次访问+1 a[++cnt] = x2; b[cnt] = node(x1,x2,y2,-1);//第二次访问-1 } sort(a+1,a+1+cnt); sort(b+1,b+1+cnt); int m = unique(a+1,a+1+cnt)-(a+1); double ans = 0; for(int i = 1;i < cnt;i++){ int l = lower_bound(a+1,a+1+m,b[i].l)-a; int r = lower_bound(a+1,a+1+m,b[i].r)-a; update(1,1,m,l,r-1,b[i].f);//因为区间有些地方可能有重复，所以需要考虑左闭右开 ans += tree[1]*(b[i+1].h-b[i].h); } printf("Test case #%d\n",flag); printf("Total explored area: %.2lf\n\n",ans); }