poj2482--Stars in Your Window(扫描线)

2024-08-25 00:48
文章标签 window 扫描线 stars poj2482

本文主要是介绍poj2482--Stars in Your Window(扫描线),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:点击打开链接

链接题目大意:给出n个星星的坐标,每个星星有一个亮度,给出一个矩形的长和宽,问矩形能包括的星星的最大亮度和(不包括边框)。

假设每个星星都是矩形的最左下点,那么每一个星星都可以得到一个矩形,(x,y)->(x,y,x+w,y+h),这个矩形的两条高边的值也就是星星的亮度k和-k,对于不同的矩形来说,如果高线出现重合部分,那么也就是说这两个星是可以出现在同一个矩形中的,扫描线求出可能出现的最大的亮度和。

注意:因为不包括边框,所以扫描时应先扫描值为负的高线,并且仅对值为正的高线统计最大值。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
#define LL __int64
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2,r,rt<<1|1
#define root 1,num_y,1
#define int_rt int l,int r,int rt
struct node{LL x , y1 , y2 ;LL k ;
}p[30000];
LL y[30000] ;
int cnt , num_y ;
struct node1{LL max1 , l , r , lazy ;
}cl[200000];
int cmp(node a,node b) {return a.x < b.x || ( a.x == b.x && a.k < 0 ) ;
}
void push_up(int rt) {cl[rt].max1 = max(cl[rt<<1].max1,cl[rt<<1|1].max1) + cl[rt].lazy;
}
void create(int_rt) {cl[rt].max1 = cl[rt].lazy = 0 ;cl[rt].l = y[l] , cl[rt].r = y[r] ;if( r - l == 1 ) {return ;}create(lson) ;create(rson) ;push_up(rt) ;
}
void update(LL ll,LL rr,LL k,int rt) {if( cl[rt].l >= ll && cl[rt].r <= rr ) {cl[rt].lazy += k ;cl[rt].max1 += k ;return ;}if( ll < cl[rt<<1].r )update(ll,min(rr,cl[rt<<1].r),k,rt<<1) ;if( rr > cl[rt<<1|1].l )update(max(cl[rt<<1|1].l,ll),rr,k,rt<<1|1) ;push_up(rt) ;
}
int main() {LL n , w , h , xx , yy , k , max1 ;int i , j ;while( scanf("%I64d %I64d %I64d", &n, &w, &h) != EOF ) {cnt = 0 , num_y = 1 ;max1 = 0 ;for(i = 1 ; i <= n ; i++) {scanf("%I64d %I64d %I64d", &xx, &yy, &k) ;p[cnt].x = xx ; p[cnt].y1 = yy ; p[cnt].y2 = yy+h ;p[cnt++].k = k ;p[cnt].x = xx+w ; p[cnt].y1 = yy ; p[cnt].y2 = yy+h ;p[cnt++].k = -k ;y[num_y++] = yy ;y[num_y++] = yy+h ;}sort(y+1,y+num_y) ;num_y = unique(y+1,y+num_y) - (y+1) ;sort(p,p+cnt,cmp) ;create(root) ;for(i = 0 ; i < cnt ; i++) {update(p[i].y1,p[i].y2,p[i].k,1) ;if( p[i].k  > 0 )max1 = max(max1,cl[1].max1) ;}printf("%I64d\n", max1) ;}return 0 ;
}


这篇关于poj2482--Stars in Your Window(扫描线)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1104085

相关文章

js window.addEventListener 是什么?

window.addEventListener 是 JavaScript 中的一个方法,用于向指定对象(在这个情况下是 window 对象,代表浏览器窗口)添加事件监听器,以便在该对象上发生特定事件时执行相应的函数(称为事件处理函数或事件监听器)。 这个方法接受三个参数: 事件类型(type):一个字符串,表示要监听的事件类型。例如,"click" 表示鼠标点击事件,"load" 表示页面加

Qt中window frame的影响

window frame 在创建图形化界面的时候,会创建窗口主体,上面会多出一条,周围多次一圈细边,这就叫window frame窗口框架,这是操作系统自带的。 这个对geometry的一些属性有一定影响,主要体现在Qt坐标系体系: 窗口当中包含一个按钮,这个按钮的坐标系是以父元素为参考,那么这个参考是widget本体作为参考,还是window frame作为参考,这两种参考体系都存在

Caused by: android.view.WindowManager$BadTokenException: Unable to add window -- token android.os.B

一个bug日志 FATAL EXCEPTION: main03-25 14:24:07.724: E/AndroidRuntime(4135): java.lang.RuntimeException: Unable to start activity ComponentInfo{com.syyx.jingubang.ky/com.anguotech.android.activity.Init

最初的window

不知你是否也是一个常年在MFC下编程的程序员,有的时候是否忘记了在MFC之前是如何写画窗口的了呢,或者你从来都只是机械的在MFC下面写代码,已经麻木了。其实有一个很简单的方法,或许能够帮你更清楚的了解WINDOW是怎么产生的。 随便用什么版本的VS,在创建win32工程的时候,直接创建WINDOW类型的就OK了。然后,来研究下产生的源代码吧。 // Global Variables:H

VC环境下window网络程序:UDP Socket程序

最近在学Windows网络编程,正好在做UDPsocket的程序,贴上来: 服务器框架函数:              socket();    bind();    recfrom();  sendto();  closesocket(); 客户机框架函数:            socket();      recfrom();  sendto();  closesocket();

Window下编译OpenJDK17

本文详细介绍Window下如何编译OpenJDK17,包含源码路径,各工具下载地址,严格按照文章中的步骤来操作,你将获得一个由自己亲手编译出的jdk。  一、下载OpenJDK17源码 下载地址:GitHub - openjdk/jdk at jdk-17+35 说明: 1、kkgithub为github的国内镜像,能够提高下载速度  2、下载下来的源码存放路径:无中文、无空格

POJ 2823 Sliding Window(线段树入门)

题意: 8 31 3 -1 -3 5 3 6 7 一串数列,有一个窗口大小为3,从数列开始往后移动,输出最大和最小值。 -1 -3 -3 -3 3 33 3 5 5 6 7 窗口大小为3 思路: 维护一个线段树,代码很详细 解题心得: 因为关键值的输入量有1000000,也就是叶节点有1000000个,总节点按理说是2000000-1,但这题得开3000000才能过

Flink原理与实现:Window的实现原理

硬刚大数据系列文章链接: 2021年从零到大数据专家的学习指南(全面升级版) 2021年从零到大数据专家面试篇之Hadoop/HDFS/Yarn篇 2021年从零到大数据专家面试篇之SparkSQL篇 2021年从零到大数据专家面试篇之消息队列篇 2021年从零到大数据专家面试篇之Spark篇 2021年从零到大数据专家面试篇之Hbase篇

Apache Flink:Keyed Window与Non-Keyed Window

Apache Flink中,Window操作在流式数据处理中是非常核心的一种抽象,它把一个无限流数据集分割成一个个有界的Window(或称为Bucket),然后就可以非常方便地定义作用于Window之上的各种计算操作。本文我们主要基于Apache Flink 1.4.0版本,说明Keyed Window与Non-Keyed Window的基本概念,然后分别对与其相关的WindowFunction

Flink实战案例(二十三):自定义时间和窗口的操作符(四)window functions之增量聚合函数(一)ReduceFunction

实例一 例子: 计算每个传感器15s窗口中的温度最小值 val minTempPerWindow = sensorData.map(r => (r.id, r.temperature)).keyBy(_._1).timeWindow(Time.seconds(15)).reduce((r1, r2) => (r1._1, r1._2.min(r2._2))) 实例二 ReduceFun