xiaoguozi's Blog
Pay it forword - 我并不觉的自豪,我所尝试的事情都失败了······习惯原本生活的人不容易改变,就算现状很糟,他们也很难改变,在过程中,他们还是放弃了······他们一放弃,大家就都是输家······让爱传出去,很困难,也无法预料,人们需要更细心的观察别人,要随时注意才能保护别人,因为他们未必知道自己要什么·····
//回忆系列:
//可以优化的,去除重复点,我这没这一步,而且我比较懒,直接把离散这一步省略了,直接替代了
//不过离散化+线段树思想是不变的,注释比较少
  1//segment tree template
  2#include <iostream>
  3#include <algorithm>
  4
  5using namespace std;
  6struct Eage{
  7    long long xi;
  8    long long yu,yd;
  9    int flag;
 10    bool operator<(const Eage& e)const{
 11        return xi<e.xi;
 12    }
;
 13}
line[80210];
 14long long dy[80210];
 15
 16struct Tnode{
 17    //point left,right child
 18    Tnode *lc,*rc;
 19    //segment devide
 20    int left,right;
 21
 22    //extra
 23    int cnt;//是否覆盖
 24    long long len;//测度
 25    long long yu,yd;
 26    //construct function
 27    Tnode(int data=0,int l=0,int r=0,Tnode*lp=0,Tnode*rp=0)
 28            :left(l),right(r),lc(lp),rc(rp){
 29                len=yu=yd=0.0;
 30                cnt=0;
 31    }
;
 32}
;
 33
 34//maxsize number of Tnode
 35const int N=80002;
 36
 37//static allocate memory for Tnode [a,b] node_size=2*(b-a)+1 for [i,i+1]
 38Tnode node[N<<1];
 39//count for usage Tnode array
 40int cnt=0;
 41
 42//make a new node ,return Tnode*
 43Tnode* new_node(){
 44    Tnode* p=&node[cnt++];
 45    memset(p,0,sizeof(Tnode));
 46    return p;
 47}

 48
 49//make tree ,return Tnode* which is root
 50//parament: [left,right]
 51Tnode* make_tree(int left,int right){
 52    //make a new Tnode 
 53    Tnode* root=new_node();
 54    //Initial the Tndoe
 55    root->left=left,root->right=right;
 56    
 57    if(left+1==right){
 58        root->yu=dy[right];
 59        root->yd=dy[left];
 60        return root;
 61    }
else{
 62        int mid=(left+right)>>1;
 63        root->lc=make_tree(left,mid);
 64        root->rc=make_tree(mid,right);
 65        return root;
 66    }

 67}

 68long long CalLen(Tnode* root){
 69    root->len=0;
 70    if(root->cnt>0){
 71        root->len=dy[root->right] - dy[root->left];
 72        return root->len;
 73    }

 74    if(root->lc)root->len=root->lc->len;
 75    if(root->rc)root->len+=root->rc->len;
 76
 77    return root->len;
 78}
;
 79void Update(Tnode* root,Eage data){
 80    if(dy[root->left]>=data.yd&&dy[root->right]<=data.yu){
 81        root->cnt+=data.flag;
 82        CalLen(root);
 83        return ;
 84    }

 85    int mid=(root->left+root->right)>>1;
 86    if(dy[mid]>=data.yu){
 87        Update(root->lc,data);
 88    }
else if(dy[mid]<=data.yd){
 89        Update(root->rc,data);
 90    }
else{
 91        Eage tmp=data;
 92        tmp.yu=dy[mid];
 93        Update(root->lc,tmp);
 94
 95        tmp=data;
 96        tmp.yd=dy[mid];
 97        Update(root->rc,tmp);
 98    }

 99    CalLen(root);
100    return ;
101}

102int main()
103{
104    int e=1;
105    int n;
106    while(cin>>n){
107        cnt=0;
108        long long x1,y1,x2,y2;
109        for(int i=1;i<=2*n;i+=2){
110            cin>>x1>>x2>>y2;
111            y1=0;
112            line[i].xi=x1,line[i].yd=y1,line[i].yu=y2,line[i].flag=1;
113            line[i+1].xi=x2,line[i+1].yd=y1,line[i+1].yu=y2,line[i+1].flag=-1;
114            dy[i]=y1;
115            dy[i+1]=y2;
116        }

117        sort(line+1,line+2*n+1);
118        sort(dy+1,dy+2*n+1);
119        Tnode *root=make_tree(1,2*n);
120
121        long long area=0;
122        Update(root,line[1]);
123        for(int i=2;i<=2*n;i++){
124            area+=root->len*(line[i].xi-line[i-1].xi);
125            Update(root,line[i]);
126        }

127        //printf("Test case #%d\n",e++);
128        printf("%lld\n",area);
129    }

130    return 0;
131}
..
http://acm.pku.edu.cn/JudgeOnline/problem?id=3277
posted on 2009-03-09 14:27 小果子 阅读(1184) 评论(0)  编辑 收藏 引用 所属分类: Acm

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