算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
题目描述:
    给N(N<5000)个矩形,求周长并。
吐槽:
1. 因为最近的精力都放在数电试验和大作业上,所以博客不常更新了 ... 就算更新也会写一些好做的模板题
2. 依旧是扫描线 ... ym傻崽大神
算法分析:
    扫描线法求周长并,其中用线段树维护横向线段的加入与删除操作。
    有个很重要的地方就是一定要先加边再删除边。
 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<cstdio>
 6 using namespace std;
 7 #define lson pos<<1,L,mid
 8 #define rson pos<<1|1,mid+1,R
 9 #define left LL
10 #define right RR
11 const int N = 22005;
12 int seg[N<<2], left[N<<2], right[N<<2], cnt[N<<2], sum[N<<2];
13 void pushup(int pos, int L,int R){
14     if(cnt[pos]) {
15         seg[pos] = 1;
16         left[pos] = right[pos] = 1;
17         sum[pos] = R-L+1;
18     }
19     else if(L==R) {
20         seg[pos] = 0;
21         sum[pos] = 0;
22         left[pos] = right[pos] = 0;
23     }
24     else {
25         seg[pos] = seg[pos<<1] + seg[pos<<1|1] - (right[pos << 1] && left[pos << 1|1]);
26         left[pos] = left[pos<<1];
27         right[pos] = right[pos<<1|1];
28         sum[pos] = sum[pos<<1] + sum[pos <<1|1];
29     }
30 }
31 void update(int l,int r,int pos, int L,int R,int c){
32     if(l <= L && R<= r){
33         cnt[pos] += c;
34         pushup(pos, L, R);
35         return ;
36     }
37     int mid = L + R >> 1;
38     if(l <= mid) update(l,r,lson,c);
39     if(r > mid) update(l,r,rson,c);
40     pushup(pos , L, R);
41 }
42 struct segment{
43     int l,r,h,p;
44     segment(){}
45     segment(int L,int R,int H,int P): l(L), r(R), h(H), p(P){}
46     bool operator < (const segment A) const {
47         if(h == A.h) return p > A.p;
48         return h < A.h;
49     }
50 }num[N];
51 int main(){
52     int n;
53     while(~scanf("%d",&n)){
54         int len = 0;
55         for(int i=0;i<n;i++){
56             int x0,y0,x1,y1;
57             scanf("%d%d%d%d",&x0,&y0,&x1,&y1);
58             num[len++] = segment(x0,x1-1,y0,1);
59             num[len++] = segment(x0,x1-1,y1,-1);
60         }
61         sort(num,num+len);
62         int last = 0, ans = 0;
63         memset(cnt,0,sizeof(cnt));
64         memset(sum,0,sizeof(sum));
65         memset(seg,0,sizeof(seg));
66         memset(left,0,sizeof(left));
67         memset(right,0,sizeof(right));
68         for(int i=0;i<len-1; i++){
69             update(num[i].l,num[i].r,1,-10000,10000,num[i].p);
70             ans += abs(sum[1]-last) ;
71             last = sum[1];
72             ans += (num[i+1].h-num[i].h) * seg[1] * 2;
73         }
74         ans += sum[1];
75         cout<<ans<<endl;
76     }
77 }
78 
posted on 2012-06-04 20:54 西月弦 阅读(447) 评论(0)  编辑 收藏 引用 所属分类: 解题报告经典题目

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理