锐客网

  1. 首页 > 睿知 > it技术 > >

2017 ACM-ICPC 亚洲区（南宁赛区）网络赛Overlapping Rectangles矩形并面积和

IT知识overlapping网络赛亚洲区

大鹏一日同风起，扶摇直上九万里。这篇文章主要讲述2017 ACM-ICPC 亚洲区（南宁赛区）网络赛Overlapping Rectangles矩形并面积和相关的知识，希望能为你提供帮助。
Overlapping Rectangles
题意：求 n 个矩形并面积和
tags：扫描线+线段树，模板题
【2017 ACM-ICPC 亚洲区（南宁赛区）网络赛Overlapping Rectangles矩形并面积和】参考博客

#include< bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i< =b; ++i) #define per(i,b,a) for (int i=b; i> =a; --i) #define mes(a,b)memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fifirst #define sesecond typedef long long ll; const int N=1000+5; int col[N< < 3], cnt, res; double X[N< < 3], Sum[N< < 3], Sum2[N< < 3]; //多开一倍，因为 x坐标有两个 struct Seg { double l, r, h; int flag; Seg(){} Seg(double l,double r,double h,int flag):l(l),r(r),h(h),flag(flag){} bool operator < (const Seg & object ) const{ return h < object.h; } }S[N< < 2]; void pushup(int ro, int l, int r) { if(col[ro])//覆盖一次 Sum[ro]=X[r+1]-X[l]; else if(l==r) Sum[ro]=0; else Sum[ro]=Sum[ro< < 1]+Sum[ro< < 1|1]; if(col[ro]> =2) // 覆盖两次以上 Sum2[ro]=X[r+1]-X[l]; else if(l==r) Sum2[ro]=0; else if(col[ro]==1) Sum2[ro]=Sum[ro< < 1] +Sum[ro< < 1|1]; else if(col[ro]==0) Sum2[ro]=Sum2[ro< < 1] +Sum2[ro< < 1|1]; } void update(int L, int R, int c, int ro, int l, int r)// [l,r]当前区间，[L,R]目标区间 { if(L< =l & & r< =R) { col[ro] += c; pushup(ro, l, r); return ; } int mid = (l+r)> > 1; if(L< =mid) update(L, R, c, ro< < 1, l, mid); if(R> mid) update(L, R, c, ro< < 1|1, mid+1, r); pushup(ro, l, r); } int binary_find(double x) { int l=1, r=res, ans, mid; while(l< =r) { mid = (l+r)> > 1; if(X[mid] > = x) ans=mid, r=mid-1; else l=mid+1; } return ans; } double solve(int n) { cnt = res = 0; for(int i=1; i< =n; ++i) { double x1, y1, x2, y2; scanf("%lf %lf %lf %lf", & x1, & y1, & x2, & y2); S[++cnt]=Seg(x1,x2,y1,1); X[cnt]=x1; S[++cnt]=Seg(x1,x2,y2,-1); X[cnt]=x2; } sort(X+1, X+1+cnt); sort(S+1, S+1+cnt); ++res; for(int i=2; i< =cnt; ++i) {// 去重，x坐标过大的话，就离散化 if(X[i]!=X[i-1])X[++res]=X[i]; } memset(Sum, 0, sizeof(Sum)); memset(col, 0, sizeof(col)); memset(Sum2, 0, sizeof(Sum2)); double ans=0; for(int i=1; i< cnt; ++i) { int l = binary_find(S[i].l); //二分左端点 int r = binary_find(S[i].r)-1; // 左闭右开,二分右端点 update(l, r, S[i].flag, 1, 1, res); ans += Sum[1]*(S[i+1].h-S[i].h); //矩阵并 //ans += Sum2[1]*(S[i+1].h-S[i].h); //矩阵交集 } return ans; }int main() { int n; while(scanf("%d", & n), n) { printf("%.0f\n", solve(n)); } puts("*"); return 0; }


    推荐阅读


    上一篇：hdu6206Applejava，三点找外接圆

    下一篇：shopexapp开发机制