http://acm.hdu.edu.cn/showproblem.php?pid=1542
面积并
- #include<bits/stdc++.h>
- #define maxn 100005
- #define lson l,mid,rt<<1
- #define rson mid+1,r,rt<<1|1
- #define pb push_back
- using namespace std;
- double tree[maxn<<2];
- int lazy[maxn<<2];
- vector<double>ve;
- 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 &b)const{
- return h<b.h;
- }
- }s[maxn];
- void push_up(int l,int r,int rt){
- if(lazy[rt]){
- tree[rt]=ve[r]-ve[l-1];
- }
- else if(l==r){
- tree[rt]=0;
- }
- else{
- tree[rt]=tree[rt<<1]+tree[rt<<1|1];
- }
- }
- void build(int l,int r,int rt){
- tree[rt]=0,lazy[rt]=0;
- if(l==r) return;
- int mid=l+r>>1;
- build(lson);
- build(rson);
- }
- void add(int L,int R,int v,int l,int r,int rt){
- if(L<=l&&R>=r){
- lazy[rt]+=v;
- push_up(l,r,rt);
- return;
- }
- int mid=l+r>>1;
- if(L<=mid) add(L,R,v,lson);
- if(R>mid) add(L,R,v,rson);
- push_up(l,r,rt);
- }
- int getid(double x){
- return lower_bound(ve.begin(),ve.end(),x)-ve.begin()+1;
- }
- int main(){
- int n;
- int Case=1;
- while(~scanf("%d",&n)){
- if(!n) break;
- ve.clear();
- int tot=0;
- double x1,y1,x2,y2;
- for(int i=1;i<=n;i++){
- scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
- ve.pb(x1),ve.pb(x2);
- s[++tot]=seg(x1,x2,y1,1);
- s[++tot]=seg(x1,x2,y2,-1);
- }
- sort(ve.begin(),ve.end());
- ve.erase(unique(ve.begin(),ve.end()),ve.end());
- sort(s+1,s+tot+1);
- int N=ve.size();
- build(1,N,1);
- double ans=0;
- for(int i=1;i<tot;i++){
- int L=getid(s[i].l);
- int R=getid(s[i].r)-1;
- add(L,R,s[i].flag,1,N,1);
- ans+=tree[1]*(s[i+1].h-s[i].h);
- }
- printf("Test case #%d\n",Case++);
- printf("Total explored area: %.2f\n\n",ans);
- }
- }
- View Code
- http://acm.hdu.edu.cn/showproblem.php?pid=1255
面积交
- #include<bits/stdc++.h>
- #define maxn 100005
- #define lson l,mid,rt<<1
- #define rson mid+1,r,rt<<1|1
- #define pb push_back
- using namespace std;
- double tree[maxn<<2],tree2[maxn<<2];
- int lazy[maxn<<2];
- vector<double>ve;
- 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 &b)const{
- return h<b.h;
- }
- }s[maxn];
- void push_up(int l,int r,int rt){
- if(lazy[rt]){
- tree[rt]=ve[r]-ve[l-1];
- }
- else if(l==r){
- tree[rt]=0;
- }
- else{
- tree[rt]=tree[rt<<1]+tree[rt<<1|1];
- }
- }
- void push_up2(int l,int r,int rt){
- if(lazy[rt]>1){
- tree2[rt]=ve[r]-ve[l-1];
- }
- else if(l==r){
- tree2[rt]=0;
- }
- else if(lazy[rt]==1){
- tree2[rt]=tree[rt<<1]+tree[rt<<1|1];
- }
- else{
- tree2[rt]=tree2[rt<<1]+tree2[rt<<1|1];
- }
- }
- void build(int l,int r,int rt){
- tree[rt]=0,lazy[rt]=0;
- if(l==r) return;
- int mid=l+r>>1;
- build(lson);
- build(rson);
- }
- void add(int L,int R,int v,int l,int r,int rt){
- if(L<=l&&R>=r){
- lazy[rt]+=v;
- push_up(l,r,rt);
- push_up2(l,r,rt);
- return;
- }
- int mid=l+r>>1;
- if(L<=mid) add(L,R,v,lson);
- if(R>mid) add(L,R,v,rson);
- push_up(l,r,rt);
- push_up2(l,r,rt);
- }
- int getid(double x){
- return lower_bound(ve.begin(),ve.end(),x)-ve.begin()+1;
- }
- int main(){
- int n;
- int Case=1;
- int T;
- scanf("%d",&T);
- while(T--){
- scanf("%d",&n);
- ve.clear();
- int tot=0;
- double x1,y1,x2,y2;
- for(int i=1;i<=n;i++){
- scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
- ve.pb(x1),ve.pb(x2);
- s[++tot]=seg(x1,x2,y1,1);
- s[++tot]=seg(x1,x2,y2,-1);
- }
- sort(ve.begin(),ve.end());
- ve.erase(unique(ve.begin(),ve.end()),ve.end());
- sort(s+1,s+tot+1);
- int N=ve.size();
- build(1,N,1);
- double ans=0;
- for(int i=1;i<tot;i++){
- int L=getid(s[i].l);
- int R=getid(s[i].r)-1;
- add(L,R,s[i].flag,1,N,1);
- ans+=tree2[1]*(s[i+1].h-s[i].h);
- }
- printf("%.2f\n",ans);
- }
- }
- View Code
来源: http://www.bubuko.com/infodetail-3054669.html