手机版网站怎么做的,简单的网站怎么做的,网站结构设计,上海市工程咨询行业协会官网题目链接#xff1a;点击打开链接 题目描写叙述#xff1a;给定一些矩形#xff0c;求这些矩形的总面积。假设有重叠。仅仅算一次 解题思路#xff1a;扫描线线段树离散#xff08;代码从上往下扫描#xff09; 代码#xff1a; #includecstdio
#include al… 题目链接点击打开链接 题目描写叙述给定一些矩形求这些矩形的总面积。假设有重叠。仅仅算一次 解题思路扫描线线段树离散代码从上往下扫描 代码 #includecstdio
#include algorithm
#define MAXN 110
#define LL ((rt1)1)
#define RR ((rt1)2)
using namespace std;
int n;
struct segment{double l,r,h;int f;bool operator(const segment b)const{return hb.h;}
}sg[2*MAXN];
double pos[2*MAXN];
int id;
void addSegment(double x1,double y1,double x2,double y2){sg[id].lx1;sg[id].rx2;sg[id].hy1;sg[id].f1;pos[id]x1;sg[id].lx1;sg[id].rx2;sg[id].hy2;sg[id].f-1;pos[id]x2;
}
int binary(double key,int low,int high){while(lowhigh){int mid(lowhigh)/2;if(pos[mid]key)return mid;else if(keypos[mid])highmid-1;elselowmid1;}return -1;
}
struct Tree{int l,r;int cover;double len;
}tree[8*MAXN];
void build(int rt,int l,int r){tree[rt].ll;tree[rt].rr;tree[rt].cover0;tree[rt].len0;if(lr-1)return;int mid(lr)1;build(LL,l,mid);build(RR,mid,r);
}
void pushup(int rt){if(tree[rt].cover)tree[rt].lenpos[tree[rt].r]-pos[tree[rt].l];else if(tree[rt].ltree[rt].r-1)tree[rt].len0;elsetree[rt].lentree[LL].lentree[RR].len;
}
void update(int rt,int l,int r,int f){if(tree[rt].lltree[rt].rr){tree[rt].coverf;pushup(rt);return;}int mid(tree[rt].ltree[rt].r)1;if(rmid)update(LL,l,r,f);else if(lmid)update(RR,l,r,f);else{update(LL,l,mid,f);update(RR,mid,r,f);}pushup(rt);
}
int main(){int Case0;while(scanf(%d,n)!EOFn!0){id0;double x1,y1,x2,y2;for(int i0;in;i){scanf(%lf%lf%lf%lf,x1,y1,x2,y2);addSegment(x1,y1,x2,y2);}n(n1);sort(sg,sgn);sort(pos,posn);int m1;for(int i1;in;i)if(pos[i]!pos[i-1])pos[m]pos[i];build(0,0,m-1);double ans0;int lbinary(sg[0].l,0,m-1);int rbinary(sg[0].r,0,m-1);update(0,l,r,sg[0].f);for(int i1;in;i){ans(sg[i-1].h-sg[i].h)*tree[0].len;lbinary(sg[i].l,0,m-1);rbinary(sg[i].r,0,m-1);update(0,l,r,sg[i].f);}printf(Test case #%d\n,Case);printf(Total explored area: %.2f\n\n,ans);}return 0;
}转载于:https://www.cnblogs.com/brucemengbm/p/7107406.html
