SGU 319 Kalevich Strikes Back(线段树扫描线)

SGU 319 Kalevich Strikes Back(线段树扫描线)

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

题目大意:

n个矩形,将一个大矩形分成 n+1 块。矩形之间不重合,可是包括。求这n+1个矩形的面积

思路分析:

用线段树记录他们之间的父子关系。然后dfs 计算面积。

当给出的矩形上边的时候,就要记录到该矩形的父亲去。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define lson num<<1,s,mid
#define rson num<<1|1,mid+1,e
#define maxn 70010

using namespace std;
typedef long long LL;

int cov[maxn<<2];
LL area[maxn<<1];
int W,H;

struct node
{
    int s,e,h,type;
    bool operator < (const node &cmp)const
    {
        return h<cmp.h;
    }
}scline[maxn<<1];

struct foo
{
    int s,e,h;
}sqr[maxn<<2];

int x[maxn<<1];
int pre[maxn<<1];

void pushdown(int num)
{
    if(cov[num]!=-1){
        cov[num<<1]=cov[num<<1|1]=cov[num];
        cov[num]=-1;
    }
}
void build(int num,int s,int e)
{
    cov[num]=0;
    if(s==e)return;
    int mid=(s+e)>>1;
    build(lson);
    build(rson);
}

void update(int num,int s,int e,int l,int r,int val)
{
    if(l<=s && r>=e)
    {
        if(val<0)cov[num]=pre[abs(val)];
        else cov[num]=val;
        return;
    }
    pushdown(num);
    int mid=(s+e)>>1;
    if(l<=mid)update(lson,l,r,val);
    if(r>mid)update(rson,l,r,val);
}

int PRE;
int query(int num,int s,int e,int l,int r)
{


    if(cov[num]!=-1)
    {
        return cov[num];
    }
    pushdown(num);
    int mid=(s+e)>>1;
    if(r<=mid)return query(lson,l,r);
    else if(l>mid)return query(rson,l,r);
    else return query(lson,l,mid);
}

int head[maxn<<1];
int next[maxn<<1];
int to[maxn<<1];
int tot;
void add(int a,int b)
{
    next[tot]=head[a];
    head[a]=tot;
    to[tot]=b;
    tot++;
}
LL getarea(int index)
{
    return (LL)sqr[index].h*(LL)(sqr[index].e-sqr[index].s);
}
void dfs(int x)
{
    for(int s=head[x];s!=0;s=next[s])
    {
        area[x]-=getarea(to[s]);
        dfs(to[s]);
    }
}

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        tot=1;

        memset(pre,0,sizeof pre);

        scanf("%d%d",&W,&H);
        area[0]=(LL)W*(LL)H;
        sqr[0].s=0;sqr[0].e=W;sqr[0].h=H;
        for(int i=1;i<=n;i++)
        {
            int x1,y1,x2,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

            if(x1>x2)swap(x1,x2);
            if(y1>y2)swap(y1,y2);
            sqr[i].s=x1;sqr[i].e=x2;sqr[i].h=y2-y1;

            scline[2*i-1].s=x1;
            scline[2*i-1].e=x2;
            scline[2*i-1].h=y1;
            scline[2*i-1].type=i;
            x[2*i-1]=x1;

            scline[2*i].s=x1;
            scline[2*i].e=x2;
            scline[2*i].h=y2;
            scline[2*i].type=-i;
            x[2*i]=x2;
        }

        x[2*n+1]=0;
        x[2*n+2]=W;

        for(int i=1;i<=n;i++)
        area[i]=getarea(i);

        sort(x+1,x+2*n+3);
        int m=unique(x+1,x+2*n+3)-(x+1)-1;

        build(1,0,m);

        sort(scline+1,scline+2*n+1);
        memset(head,0,sizeof head);
        tot=1;
        for(int i=1;i<=2*n;i++)
        {
            int l=lower_bound(x+1,x+m+1,scline[i].s)-(x+1);
            int r=lower_bound(x+1,x+m+1,scline[i].e)-(x+1);


            if(scline[i].type>0)
            {
                pre[scline[i].type]=query(1,0,m,l,r);
                printf("%d %d\n",scline[i].type,pre[scline[i].type]);
                add(pre[scline[i].type],scline[i].type);
               
            }
            update(1,0,m,l,r,scline[i].type);
        }

        dfs(0);
        sort(area,area+n+1);

        for(int i=0;i<=n;i++)
        printf("%lld%c",area[i],i==n?'\n':' ');
    }
    return 0;
}
/*
2
5 5
1 1 4 4
2 2 3 3

4
10 10
1 1 5 5
2 2 3 4
6 1 9 9
7 2 8 3

4
10 10
1 1 9 6
2 2 5 5
2 7 8 9
3 6 5 7
*/

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118539.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • the section of the README devoted to missing data problems[通俗易懂]

    the section of the README devoted to missing data problems[通俗易懂]the section of the README devoted to missing data problems

  • docker修改mysql密码_mysql重新设置密码

    docker修改mysql密码_mysql重新设置密码进入容器dockerexec-it{容器ID}/bin/bash调整MySQL配置文件,设置跳过权限控制:echo”skip-grant-tables”>>/etc/mysql/conf.d/docker.cnf警告:这就意味着任何用户都能登录进来,并进行任何操作,相当不安全。退出容器:exit重启容器:dockerrestart{容器ID}再次进入容器:dockerexec-it{容器ID}/bin/bash登录mysql(无需密码):my.

    2022年10月15日
  • Java连接MySQL mysql-connector-java-bin.jar驱动包的下载与安装

    Java连接MySQL mysql-connector-java-bin.jar驱动包的下载与安装eclipse在连接mysql数据库的时候要通过mysql驱动包进行连接首先进入官网中—-官网地址:https://dev.mysql.com/进入官网中选择DOWNLOADS(下载)2.选择下载中的mysql-connectors3.选择connector/JJ指的是Java4.接下在选择操作系统,此处选择platformindependent(独立于平台)…

  • JAVA枚举类型(Enum)的使用[通俗易懂]

    JAVA枚举类型(Enum)的使用[通俗易懂]在现实社会中,有些类的实例对象是固定的。例如季节,只有春夏秋冬。如果你创建了一个season类,你当然有义务维护这个类的实例对象只能是春(SPRING)、夏(SUMMER)、秋(AUTUMN)、冬(WINTER)这四个。这个时候就体现出枚举类的作用了,java中枚举类型就是针对这样的场景需求所设计的。/***枚举类的后缀建议为Enum,枚举类型的实例对象建议全大写(这样做符合JAVA的…

  • 科学计算机度转弧度,角度弧度换算器在线(70°角度转换弧度)

    科学计算机度转弧度,角度弧度换算器在线(70°角度转换弧度)1°=0.01745rad1rad=57.30°计算过程:1°=π/180≈0.01745rad1rad=180/π=57.30°扩展资料:数学上是用弧度而非角度,因为360的容易整除对数学不重要,而数.角度是DEG,弧度是RAD,梯度是GRA。转换模式的方法是按MODE,然后按相应的键。不同型号可能不一样求采纳!!!!!!!!!!1弧度=180/π度1度=…

  • 用R语言绘制ROC曲线

    用R语言绘制ROC曲线1roc曲线的意义ROC曲线就是用来判断诊断的正确性,最理想的就是曲线下的面积为1,比较理想的状态就是曲线下的面积在0.8-0.9之间,0.5的话对实验结果没有什么影响。如图:2代码部分install.packages(“pROC”)install.packages(“ggplot2”)library(pROC)library(ggplot2)#建立曲线data(aSAH)…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号