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

POJ - 1151(线段树+扫描线)

程序员文章站 2022-07-13 11:09:49
...

题目:click
题意:给出了矩形的左上角以及右下角的坐标,求所有矩阵构成的图形的面积。
思路:先给出扫描线的定义,图是偷的。。。。

POJ - 1151(线段树+扫描线)可以看到,实质上给定的n个矩形,平行于y轴的有2 * n个,同理x轴,将线全部延长就分割成了许多的小矩形,可以从一边入手,上图是以平行于x轴去扫描的,确定从上或者从下开始,扫描每次碰到的边需要分为入边或者出边,入边时需要加长度,出边相反就不需要计算这条出边之后的贡献。
那么依然是从上到下平行于x轴去扫描的,垂直于x轴的段我们不知道,要计算矩形的面积就需要,我们知道了高,就需要知道x轴的长段之后相乘即可。线段树就是为了去维护x轴的段,之前说了分割成里2*n条线,即2*n-1段,线记录标号,去维护一段的长度。由于线段可能重合,所以处理一下。
可见代码。(代码是平行于y轴从左到右去扫描,线段树维护y轴的段)。这里的线段树是以端点去处理的,注意一下。
思路源于:click

#include<cmath>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<istream>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<queue>
#define inf 0x3f3f3f3f
#define llinf 0x3f3f3f3f3f3f3f3f
#define MAX_len 210*4
using namespace std;
typedef long long ll;
#define m ((l+r)>>1)
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
struct A {
    int l,r;
    double left,right;
    double len;
    int cover;
}tree[MAX_len];
double y[MAX_len];
struct B{
    double x,y1,y2;
    int flag;//入边或者出边
}node[MAX_len];
void build_tree(int p,int l1,int r1)
{
    tree[p].l=l1,tree[p].r=r1;
    tree[p].left=y[l1];
    tree[p].right=y[r1];
    tree[p].len=0;
    tree[p].cover=0;
    if(tree[p].l+1==tree[p].r)
        return ;
    int mid=(l1+r1)/2;
    build_tree(p*2,l1,mid);
    build_tree(p*2+1,mid,r1);
}
void solve(int p)
{
    if(tree[p].cover>0)
    {
        tree[p].len=tree[p].right-tree[p].left;
    }
    else if(tree[p].r-tree[p].l==1)
    {
        tree[p].len=0;
    }
    else
        tree[p].len=tree[p*2].len+tree[p*2+1].len;
}
void update(int p,B temp)
{
    if(temp.y1==tree[p].left&&temp.y2==tree[p].right)
    {
        tree[p].cover+=temp.flag;
    }
    else if(temp.y2<=tree[p*2].right)
    {
        update(p*2,temp);
    }
    else if(temp.y1>=tree[p*2+1].left)
    {
        update(p*2+1,temp);
    }
    else
    {
        B tmp;
        tmp=temp;
        tmp.y2=tree[p*2].right;
        update(p*2,tmp);
        tmp=temp;
        tmp.y1=tree[p*2+1].left;
        update(p*2+1,tmp);
    }
    solve(p);
}
bool cmp(B t1,B t2)
{
    return t1.x<t2.x;
}
int main()
{
    int n;
    int yy=1;
    while(~scanf("%d",&n)&&n)
    {
        int i,j,k;
        int t=1;
        for(i=1;i<=n;i++)
        {
            scanf("%lf %lf",&node[t].x,&y[t]);
            scanf("%lf %lf",&node[t+1].x,&y[t+1]);
            node[t].y1=y[t];
            node[t].y2=y[t+1];
            node[t+1].y1=y[t];
            node[t+1].y2=y[t+1];
            node[t].flag=1;
            node[t+1].flag=-1;
            t+=2;
        }
        sort(node+1,node+t,cmp);
        sort(y+1,t+y);
        build_tree(1,1,t-1);
        update(1,node[1]);
        double ans=0;
        for(i=2;i<t;i++)
        {
            ans+=tree[1].len*(node[i].x-node[i-1].x);
            update(1,node[i]);
        }
        printf("Test case #%d\n",yy++);
        printf("Total explored area: %.2f\n\n",ans);
    }
    return 0;
}