首页 > 代码库 > 城市地平线

城市地平线

2024-07-17 02:10:21   215人阅读

把N个建筑正投影到一个竖直平面上，给出N个建筑的左右坐标值和高度，计算阴影部分的面积。

input

   第一行建筑物的个数，接下来N行，每行给出三个数， 左右坐标值 和高度。其中1，r,h《=十亿.

output 

　　面积。

 1 #include"iostream" 2 #include"cstdio" 3 #include"cstring" 4 #include"algorithm" 5 using namespace std; 6 const int ms=50001; 7 typedef long long LL; 8 struct building 9 {10     LL l,r,h;11 }line[ms];12 LL node[ms*2];13 struct tree14 {15     LL l,r,h;16 }treenode[ms*4];17 bool cmp(const building &a,const building &b)18 {19     return a.h<b.h;20 }21 void init(int n);22 void build(LL l,LL r,int p);23 void insert(LL l,LL r,LL value,int p);24 LL search(int p);25 int main()26 {27     int n;28     scanf("%d",&n);29     init(n);30     build(1,node[0],1);31     for(int i=1;i<=n;i++)32         insert(line[i].l,line[i].r,line[i].h,1);33     printf("%I64d\n",search(1));34     return 0;35 }36 void init(int n)37 {38     memset(treenode,0,sizeof(treenode));39     memset(node,0,sizeof(node));40     memset(line,0,sizeof(line));41     for(int i=1;i<=n;i++)42     {43         scanf("%I64d%I64d%I64d",&line[i].l,&line[i].r,&line[i].h);44         node[i*2-1]=line[i].l;45         node[i*2]=line[i].r;46     }47     sort(line+1,line+1+n,cmp);48     int j=1;49     sort(node+1,node+2*n+1);50     for(int i=1;i<=2*n;i++)51     {52         if(node[i]!=node[j])53             node[++j]=node[i];54     }55     node[0]=j;56     return ;57 }58 void build(LL l,LL r,int p)59 {60     treenode[p].l=node[l];61     treenode[p].r=node[r];62     //cout<<p<<" : "<<node[l]<<" : "<<node[r]<<endl;63     if(l+1==r)64         return ;65     int mid=(l+r)/2;66     build(l,mid,2*p);67     build(mid,r,2*p+1);68     return ;69 }70 void insert(LL l,LL r,LL value,int p)71 {72     if(l<=treenode[p].l&&treenode[p].r<=r)73     {74         treenode[p].h=value;75         return ;76     }77     if(treenode[p].h>0)78         treenode[p*2].h=treenode[2*p+1].h=treenode[p].h;79     treenode[p].h=-1;80     if(r>treenode[2*p].r)81         insert(l,r,value,p*2+1);82     if(l<treenode[2*p].r)83         insert(l,r,value,2*p);84     return ;85 }86 LL search(int p)87 {88     if(treenode[p].h>0)89         return treenode[p].h*(treenode[p].r-treenode[p].l);90     if(treenode[p].h==0)91         return 0;92     return (search(2*p)+search(2*p+1));93 }

 

　　


联系
我们