poj1151(线段树+扫描线)
程序员文章站
2022-07-13 11:10:25
...
题目就是矩阵面积并这里我就不多说了
这道题的精髓在于运用线段树来求边长,扫描线的思想反而没有线段树重要
直接上代码+注释
#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);
}
}