扫描线求矩形面积并。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 8 using namespace std; 9 10 #define LL long long11 #define eps 1e-812 #define inf 0x3f3f3f3f13 #define lson l, m, rt << 114 #define rson m+1, r, rt << 1 | 115 #define mnx 110016 17 double x[mnx], sum[mnx];18 int vis[mnx];19 struct edge{20 double l, r, h;21 int s;22 edge(){}23 edge( double l, double r, double h, int s ) : l(l), r(r), h(h), s(s) {}24 bool operator < ( const edge &b ) const {25 return h < b.h;26 }27 }e[mnx];28 void pushup( int rt, int l, int r ){29 if( vis[rt] ) sum[rt] = x[r+1] - x[l];30 else if( l == r ) sum[rt] = 0;31 else sum[rt] = sum[rt<<1] + sum[rt<<1|1];32 }33 void update( int L, int R, int v, int l, int r, int rt ){34 if( L <= l && R >= r ){35 vis[rt] += v;36 pushup( rt, l, r );37 return ;38 }39 int m = ( l + r ) >> 1;40 if( L <= m ) update( L, R, v, lson );41 if( R > m ) update( L, R, v, rson );42 pushup( rt, l, r );43 }44 int bin( double v, int L, int R ){45 int l = L, r = R;46 while( l < r ){47 int m = ( l + r ) >> 1;48 if( x[m] >= v ) r = m;49 else l = m + 1;50 }51 return l;52 }53 int main(){54 int n, m, k, kk = 0;55 while( scanf( "%d", &n ) != EOF && n ){56 printf( "Test case #%d\n", ++kk );57 memset( vis, 0, sizeof vis );58 for( int i = 0; i < mnx; ++i )59 sum[i] = 0;60 m = 0, k = 1;61 for( int i = 0; i < n; ++i ){62 double ax, ay, bx, by;63 scanf( "%lf %lf %lf %lf", &ax, &ay, &bx, &by );64 x[m] = ax, e[m++] = edge( ax, bx, ay, 1 );65 x[m] = bx, e[m++] = edge( ax, bx, by, -1 );66 }67 sort( x, x + m );68 sort( e, e + m );69 for( int i = 1; i < m; ++i )70 if( x[i] != x[i-1] ) x[k++] = x[i];71 double ans = 0;72 for( int i = 0; i < m-1; ++i ){73 int l = bin( e[i].l, 0, k-1 );74 int r = bin( e[i].r, 0, k-1 ) - 1;75 if( l <= r ) update( l, r, e[i].s, 0, k-1, 1 );76 ans += sum[1] * ( e[i+1].h - e[i].h );77 }78 printf( "Total explored area: %.2lf\n\n", ans );79 }80 return 0;81 }
扫描线求矩形周长并。思路:与面积不同的地方是还要记录竖的边有几个(numseg记录),并且当边界重合的时候需要合并(用lbd和rbd表示边界来辅助)
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 8 using namespace std; 9 10 #define LL long long11 #define eps 1e-812 #define lson l, m, rt << 113 #define rson m + 1, r, rt << 1 | 114 #define inf 0x3f3f3f3f15 #define mnx 2300016 17 int len[mnx<<2], cnt[mnx<<2], segsum[mnx<<2];18 bool lbd[mnx<<2], rbd[mnx<<2];19 struct edge{20 int l, r, h, s;21 edge(){}22 edge( int l, int r, int h, int s ) : l(l), r(r), h(h), s(s) {}23 bool operator < ( const edge &b ) const {24 return h < b.h || ( h == b.h && s > b.s );25 }26 }e[mnx];27 void pushup( int rt, int l, int r ){28 if( cnt[rt] ){29 len[rt] = r - l + 1;30 segsum[rt] = 2;31 lbd[rt] = rbd[rt] = 1;32 }33 else if( l == r ){34 len[rt] = segsum[rt] = lbd[rt] = rbd[rt] = 0;35 }36 else{37 len[rt] = len[rt<<1] + len[rt<<1|1];38 segsum[rt] = segsum[rt<<1] + segsum[rt<<1|1];39 lbd[rt] = lbd[rt<<1];40 rbd[rt] = rbd[rt<<1|1];41 if( rbd[rt<<1] && lbd[rt<<1|1] ) segsum[rt] -= 2;42 }43 }44 void update( int L, int R, int v, int l, int r, int rt ){45 if( L <= l && R >= r ){46 cnt[rt] += v;47 pushup( rt, l, r );48 return ;49 }50 int m = ( l + r ) >> 1;51 if( L <= m ) update( L, R, v, lson );52 if( R > m ) update( L, R, v, rson );53 pushup( rt, l, r );54 }55 int main(){56 int n, m;57 while( scanf( "%d", &n ) != EOF ){58 m = 0;59 int lmin = inf, rmax = -inf;60 for( int i = 0; i < n; ++i ){61 int ax, ay, bx, by;62 scanf( "%d%d%d%d", &ax, &ay, &bx, &by );63 e[m++] = edge( ax, bx, ay, 1 );64 e[m++] = edge( ax, bx, by, -1 );65 lmin = min( lmin, ax );66 rmax = max( rmax, bx );67 }68 sort( e, e + m );69 int ans = 0, pre = 0;70 for( int i = 0; i < m; ++i ){71 if( e[i].l < e[i].r )72 update( e[i].l, e[i].r-1, e[i].s, lmin, rmax-1, 1 );73 ans += segsum[1] * ( e[i+1].h - e[i].h );74 ans += abs( len[1] - pre );75 pre = len[1];76 }77 printf( "%d\n", ans );78 }79 return 0;80 }
矩形面积并。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 8 using namespace std; 9 10 #define LL long long11 #define eps 1e-812 #define lson l, m, rt << 113 #define rson m + 1, r, rt << 1 | 114 #define inf 0x3f3f3f3f15 #define mnx 5300016 17 struct edge{18 int l, r, h, s;19 edge () {}20 edge( int l, int r, int h, int s ) : l(l), r(r), h(h), s(s) {}21 bool operator < ( const edge &b ) const {22 return h < b.h || ( h == b.h && s > b.s );23 }24 }e[mnx];25 int cnt[mnx<<2], len[mnx<<2];26 void pushup( int rt, int l, int r ){27 if( cnt[rt] ){28 len[rt] = r - l + 1;29 }30 else if( l == r )31 len[rt] = 0;32 else33 len[rt] = len[rt<<1] + len[rt<<1|1];34 }35 void update( int L, int R, int v, int l, int r, int rt ){36 if( L <= l && R >= r ){37 cnt[rt] += v;38 pushup( rt, l, r );39 return ;40 }41 int m = ( l + r ) >> 1;42 if( L <= m ) update( L, R, v, lson );43 if( R > m ) update( L, R, v, rson );44 pushup( rt, l, r );45 }46 int main(){47 int ax, ay, bx, by;48 while( scanf( "%d%d%d%d", &ax, &ay, &bx, &by ) != EOF ){49 if( ax == -1 && ay == -1 && bx == -1 && by == -1 ) break;50 int m = 0;51 e[m++] = edge( ax, bx, ay, 1 );52 e[m++] = edge( ax, bx, by, -1 );53 while( scanf( "%d%d%d%d", &ax, &ay, &bx, &by ) ){54 if( ax == -1 && ay == -1 && bx == -1 && by == -1 ) break;55 e[m++] = edge( ax, bx, ay, 1 );56 e[m++] = edge( ax, bx, by, -1 );57 }58 sort( e, e + m );59 int ans = 0;60 for( int i = 0; i < m; ++i ){61 if( e[i].l < e[i].r )62 update( e[i].l, e[i].r-1, e[i].s, 0, 50000, 1 );63 //printf( "%d %d %d\n", len[1], e[i+1].h, e[i].h );64 ans += len[1] * ( e[i+1].h - e[i].h );65 }66 printf( "%d\n", ans );67 }68 return 0;69 }
回家种地
求只覆盖了一次的矩形的面积。思路，也是矩形面积并。记录覆盖一次以上sum[]和覆盖两次以上more[]的区间长度，然后sum[1] - more[1]就是覆盖一次的区间长度。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 9 using namespace std;10 11 #define inf 1e1612 #define eps 1e-613 #define LL long long14 #define ULL unsigned long long15 #define MP make_pair16 #define pb push_back17 #define mod 100000000918 #define lson l, m, rt<<119 #define rson m+1, r, rt<<1|120 #define mnx 20005021 22 struct edge{23 int ax, bx, y, s;24 edge( int ax = 0, int bx = 0, int y = 0, int s = 0 ) : ax(ax), bx(bx), y(y), s(s) {}25 bool operator < ( const edge &b ) const {26 return y < b.y || y == b.y && s > b.s;27 }28 }e[mnx];29 int x[mnx], vis[mnx<<1];30 LL sum[mnx<<1], more[mnx<<1];31 void pushup( int rt, int l, int r ){32 if( vis[rt] >= 2 ){33 sum[rt] = more[rt] = x[r+1] - x[l];34 }35 else if( vis[rt] == 1 ){36 sum[rt] = x[r+1] - x[l];37 if( l == r ) more[rt] = 0;38 else more[rt] = sum[rt<<1] + sum[rt<<1|1];39 }40 else{41 if( l == r ) sum[rt] = more[rt] = 0;42 else{43 sum[rt] = sum[rt<<1] + sum[rt<<1|1];44 more[rt] = more[rt<<1] + more[rt<<1|1];45 }46 }47 }48 void update( int L, int R, int s, int l, int r, int rt ){49 if( L <= l && R >= r ){50 vis[rt] += s;51 pushup( rt, l, r );52 return ;53 }54 int m = ( l + r ) >> 1;55 if( L <= m ) update( L, R, s, lson );56 if( R > m ) update( L, R, s, rson );57 pushup( rt, l, r );58 }59 int bin( int val, int l, int r ){60 while( l < r ){61 int m = ( l + r ) >> 1;62 if( x[m] >= val ) r = m;63 else l = m+1;64 }65 return l;66 }67 int main(){68 int cas, kk = 1;69 scanf( "%d", &cas );70 while( cas-- ){71 memset( vis, 0, sizeof(vis) );72 memset( sum, 0, sizeof(sum) );73 memset( more, 0, sizeof(more) );74 int n;75 scanf( "%d", &n );76 for( int i = 0; i < n; ++i ){77 int ax, ay, bx, by;78 scanf( "%d%d%d%d", &ax, &ay, &bx, &by );79 x[i] = ax, e[i] = edge( ax, bx, ay, 1 );80 x[i+n] = bx, e[i+n] = edge( ax, bx, by, -1 );81 }82 n <<= 1;83 sort( x, x + n );84 sort( e, e + n );85 int m = unique( x, x + n ) - x;86 LL ans = 0;87 for( int i = 0; i < n-1; ++i ){88 int l = bin( e[i].ax, 0, m-1 );89 int r = bin( e[i].bx, 0, m-1 ) - 1;90 if( l <= r ) update( l, r, e[i].s, 0, m-1, 1 );91 //cout << sum[1] << " " << more[1] << endl;92 ans += (LL)( sum[1] - more[1] ) * ( e[i+1].y - e[i].y );93 }94 printf( "Case %d: %I64d\n", kk++, ans );95 }96 return 0;97 }