欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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);
    }
}

poj1151(线段树+扫描线)