题目就是矩阵面积并这里我就不多说了
这道题的精髓在于运用线段树来求边长，扫描线的思想反而没有线段树重要
直接上代码+注释
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define maxn 1000 using namespace std; class node//线段树的结构我们是用一条平行于y轴的线去扫描的 { //也就是说我们这个线段树保存的是从最小的y到最大的y在某个点上的边长， //说的不行哈，等下放个图上来 public: int l,r,c; //我们要把坐标进行离散化，l和r就是离散化的坐标，c是记录覆盖的c的具体作用在callen里面讲 double lf,rf;//因为要计算长度所以lf和rf记录的是真实坐标，也就是这个节点所管的长度 double len;//len就是在某个点上这个节点所管的真实长度啦 }; class Line //line是线段 可以理解为在x上的从y1到y2的一条线段 { //这个的作用看到后面就知道啦 public: double x,y1,y2; int f; }; node segt[maxn<<2]; Line line[maxn]; double y[maxn]; bool cmp(Line a,Line b); void build(int root,int st,int en); void update(int root,Line lin); void callen(int root); int main() { int n,icase(0); double x1,y1,x2,y2; while(scanf("%d",&n)&&n) { icase++; int cou; cou=1; for (int k=1;k<=n;k++)//简单的输入输出就不说了我们把每个矩阵分为平行与y轴的两条边储存在line中 { scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2); line[cou].x=x1;line[cou].y1=y1;line[cou].y2=y2;line[cou].f=1; y[cou]=y1; cou++; line[cou].x=x2;line[cou].y1=y1;line[cou].y2=y2;line[cou].f=-1; y[cou]=y2;//y数组是用来构造线段树的保存的是每个线段的端点 cou++; } //目前我们已经有了cou-1条line sort(y+1,y+cou);//我们将y排序就相当于对y进行离散化了 sort(line+1,line+cou,cmp);//将line按x的大小进行排序 build(1,1,cou-1);//建树 /* for (int k=1;k<=20;k++) { cout<<k<<endl; cout<<segt[k].l<<" "<<segt[k].r<<endl;; cout<<segt[k].lf<<" "<<segt[k].rf<<endl; cout<<endl; }*///建树测试 double ans(0);//这个就是计算答案了 update(1,line[1]);//先加一个边进行初始化 for (int k=2;k<cou;k++)//每次计算答案都是用前一个边*间距，因为最后两个边是一样的所以这样写是可以的 { ans+=segt[1].len*(line[k].x-line[k-1].x); update(1,line[k]); } printf("Test case #%d\nTotal explored area: %.2f\n\n",icase,ans); } }