f******5
发帖数: 104 | 1 最近在看和计算几何的问题，不少问题需要这2个算法，
如果遇到用到扫描线或者interval tree， 涉及到delete操作，基本不可能写完代码吧。
网上也找不到怎么使用现成的data structure库可以用，如果面试的时候想到这2个算
法，怎么处理？
求教有经验的大牛
比如Hacking google interview中 的这道题：
Describe an algorithm that takes an unsorted array of axis-aligned
rectangles and returns any pair of rectangles that overlaps, if there is
such a pair. Axis-aligned means that all the rectangle sides are either
parallel or perpendicular to the x- and y-axis. You can assume that each
rectangle object has two variables in it: ... 阅读全帖 |
|
h****y
发帖数: 9234 | 2 觉得很牛B,那个年代,能实现这种,对着电视打,能定位
而且都是很简陋便宜的设备.
后来上网查了一下.
非常佩服设计者的智慧.....
http://zhidao.baidu.com/question/4722924.html
和我们想象的不同，光线枪不会射出光线，只能接收光线。在接收到光线后，光线枪会
把枪口对准点的信号传回给游戏机，对应的软件就会告诉主机枪口所瞄准的位置在哪里
。
那么软件又是怎么测量位置的呢？如果你仔细观察的话，当按下扳机后，无论枪口是否
对着屏幕，屏幕上总会有一道闪光，而这道由软件控制发出的白色帧就是光枪测位的关
键。在此之前我们还有必要先来看一下隔行扫描电视机的成像方式：
在PAL\NTSC的CRT电视中，扫描线是影像生成的方式。以NTSC为例，每次影像扫描时，在
六十分之一秒内并非从头到尾连续扫描525条扫描线，而是只扫描一半，也就是262.5线
，剩下一半在另外一个六十分之一秒时扫描。第一次扫描时只由上而下水平扫描奇数线
，第二次扫描时扫描偶数线。二次扫描所生成的图场（Field）就结合成一幅完整的图像
帧（Frame）。由于扫描时是以奇数、偶数扫描线做交替... 阅读全帖 |
|
发帖数: 1 | 3 这是经典的扫描线问题，解法不限于扫描线，但是用线段树未免牛刀宰鸡。参见
Airplanes in the sky, Meeting Room等等，就用扫描线解法就好。 |
|
c******e
发帖数: 545 | 4 有意思，我也来写一点感受。
我在用iz3d的显示器。
因为实验室要新配一台电脑，准备搞点好玩的东西，能想到的一个东西就是Volume
Render的立体效果，当时想到的方案基本也就是三个：
1. nvidia
2. zalman
3. iz3d
nvidia的首先淘汰了，因为编程的问题，如果本来就是directx全屏，driver就帮你处
理好了（所以对游戏很有利）。如果要自己控制就太难了，比如我用CUDA做ray
marching然后用OpenGL显示，目前想不出什么好办法。
后来在newegg上选了zalman的显示器，这个编程最容易，原理就是水平的scanline是间
隔的，奇数线和偶数线用不同方向的circular polarized glass。带上眼镜（也是
circular polarizer）之后，左眼看到所有的奇数扫描线，右眼看到所有偶数扫描线，
图像就分开了。缺点是垂直方向分辨率只有原来一半，而且据说2d模式会看到轻微的水
平扫描线。后来因为newegg断货，没买成。
iz3d的显示器是双层的，back plane就是普通显示器，front plane叠在back |
|
f*******e
发帖数: 1061 | 5 在那云飞浪卷的南海上，有一串明珠闪耀着光芒……”歌声中描绘的美丽画面就是我国
著名的南海明珠——西沙群岛。
每一个初登岛礁的人，都会由衷地发出“祖国太美了”的感叹：辽阔的蓝色海水向天际
延伸，岛礁犹如银色的丝带镶嵌在碧波之中，透过清澈海水隐约可见珊瑚像花儿一样在
水底绽放。
当然，这只是西沙的一面。待初登岛礁时的新鲜感一过，人们便会无一例外地感受到它
的另一面：无边无际的大海几乎是唯一风景，头顶的骄阳无情地炙烤着小岛，海风裹挟
着浓浓湿气，人们裸露在外的皮肤很快就会被晒黑。
在高温、髙湿、高盐的环境中，岛上的植物为了生存，进化出一种令人叹服的本能——
断枝生芽，落地生根。
西沙石岛守岛官兵畅谈爱岛守岛故事。夏锦摄
与这些绿色植物常年相伴的，是驻守在这里的海军官兵。据中国军网6月5日报道，几十
年来，海军驻西沙某水警区官兵发扬“爱国爱岛、乐守天涯”的西沙精神，像一颗颗钢
钉牢牢铆在礁盘上，艰苦奋斗、开拓创新，谱写了一曲曲守卫西沙、建设西沙的壮美赞
歌。正如官兵们所言：“海岛再小也是祖国的领土，坚守在这片国土上，才真正明白什
么叫主权神圣、寸土不让。”
一日西沙人，一生西沙情。西沙守岛兵都... 阅读全帖 |
|
a********5
发帖数: 1631 | 6 这种题标准解法（未必是最优）应该是扫描线+二分。说标准意思是可以写出模板来，
类似的题一套就行了。
但是问题是真的45分钟可以搞定？我大二时候做类似的merge矩形的题，扫描线+二分，
光写码就写了快俩小时。。后面DEBUG什么的，POJ还出各种奇奇怪怪的问题，弄了两天
才过。。 |
|
O*******d
发帖数: 20343 | 7 PAL的黑白电视带宽是6.5兆赫，625扫描线 隔行扫描，帧频50赫兹。 NTSC的黑白电视
带宽5.5兆赫，525扫描线，隔行扫描，帧频60赫兹。 彩色电视因为要和黑白电视信号
兼容，经过信号压缩后，带宽跟相应的黑白信号一样。 |
|
S*********4
发帖数: 5125 | 8 (一)引 言
正当ACT网络论坛争论美国阿波罗登月真伪吵得不可开交，反对哈姆雷特的声势四
起之时，哈姆雷特贴出了一份出乎人们意料的回帖， 他提出：“阿姆斯特朗说"鹰
已着陆"时，是在地面录音棚里说的”。
并声称他找到了“最最确凿的证据”。他
说：
前一段我还在研究登月照片，对其中种种造假的珠丝马迹提出疑问，还有
对其工程技术方面提出疑问。现在，我可以抛弃所有这些证据不谈了，我可以
抛弃所有这些技术细节不谈了。
因为我已经找到了最最确凿的证据，可以毫不犹豫地，不容丝毫怀疑地确
证，阿波罗登月是美国宇航局导演的一出空前绝后的一场好戏。美国根本没有
上过月亮。阿姆斯特郎说“鹰已着陆”时，是在地面录音棚里说的。
我不想把我这个铁的证据说穿，留着还有用呢。再说我一但说破了，明天
联邦调查局就该来找我了。我还准备留着写书呢。再说，我一但说破了，所有
持怀疑态度者不就马上接受我的结论了吗？那太便宜了。中文牛矢铺里好不容
易有了一样大家都感兴趣的话题，可以各舒己见进行辩论，不能轻易把结果说
出来嘛！
(哈姆雷特，Re:阿波罗登月是大骗局，ACT19971206)
很遗憾的是哈姆雷特的这个回帖没有把“这... 阅读全帖 |
|
y*h
发帖数: 25423 | 9
有疑问不会差资料学习吗，阿波罗计划的大部分资料都解密公开了。关于电视的问题，
你知道它用的是什么电视信号吗？不是你看的NTSC，而是慢扫描电视，场频不是60Hz，
扫描线也不是480线，所用的频带比NTSC低很多。关于跟踪的问题，根本没有所谓遥控
摄像机，摄像机有两种，一种是固定设置的，直播大部分用这种，因为是黑白或场顺序
制彩色慢扫描电视清晰度很差；另一种是宇航员手持的，跟踪宇航员的都是另一个宇航
员手持拍摄的，而且大部分都不是直播，而是电影胶片拍摄回到地面才能看的，所以这
种清晰度极高。 |
|
M******a
发帖数: 6723 | 10 2019/07/01
16:50
http://new.qq.com/omn/author/5490145
007武器
企鹅号
今天是建党98周年，在这个特殊日子里，中国海军网发布了标题为“辽宁舰曾在大雾中
险撞渔船 舰长一决定化险为夷”的官文，文章中罕见披露了辽宁号航母在2013年差
点撞船，以及2016年歼-15舰载战斗机坠毁事故的原因。
辽宁号出航
文章介绍，2013年10月一批新兵光荣加入辽宁号航母，其中就有导航雷达兵，他们负责
发现海面目标，并第一时间向舰长报告可疑目标航向、航速等情况。雷达兵就像战舰的
眼睛，声呐兵就像战舰的耳朵。雷达兵盯着海面和天空，声呐兵盯着海下，前者用眼，
后者用耳，二者就是战舰的眼睛和耳朵，是战舰获取信息的最主要途径。
之前官媒曾报道过052B型驱逐舰169武汉号导航雷达兵徐亚庆的事迹，其中描述道：“
武汉舰顶部天线飞转，雷达电波在附近海域上空交织成一张无形“天网”；雷达操控台
显示屏上，闪动着上百个芝麻大小的海情目标。徐亚庆紧盯显示屏，锐利的双眸随着雷
达扫描线一圈一圈转动。茫茫大海之上，从外军的飞机到小小的渔船，都难逃他锐利的
眼睛……”。... 阅读全帖 |
|
d*******l
发帖数: 338 | 11 我觉得是对的。扫描线加某种区间数据结构是挺常用的办法，本来我想水平线扫描，但
不好处理多个分开的区间。这题的条件使垂直线扫描比较可行，因为不会有分开的两个
区间。很不错的方法！ |
|
|
|
w********s
发帖数: 1570 | 14 第二题，growing吧
把这个点改成1，8领域看是不是还能grow改成1的点
直到不能grow为止。
扫描线也许也可以，从上到下，扫到1，表示进入，扫到下一个1表示退出，之间的点全
部染色。如果区域不知一个的话，那么先做blob extraction。
0 |
|
H*****s
发帖数: 28 | 15 augmented interval tree被考过，还是需要熟悉一下的
吧。 |
|
|
|
x*******9
发帖数: 138 | 18 跪吧。。。
除非你运气好还记得。。。
面试让写线段树。。。我觉得这真是日狗。。。 |
|
|
a********m
发帖数: 15480 | 20 冷静点应该能想到吧。从最直接的2维canvas描点，仔细考虑优化一下到1维扫描线也是
正常思路，毕竟也没啥其他的方向。难道是俺2年前看的那遍cc150还有残留印象所以不
觉得很离谱？
代码确实烦，俺是肯定写不完。但是应该意思到就差不多。
G有人店面比onsite简单一点，有人直接上onsite的题目。记得讨论哪个比较好的时候
倾向后者的多一些。 |
|
s******7
发帖数: 1758 | 21 Skyline就是标准的扫描线
优化要 HashHeap, 不然一般的heap remove的时候不是constant time. |
|
W***o
发帖数: 6519 | 22 这看起来很像空中有几架飞机的那道题啊，感觉用扫描线会比较简单 |
|
b****t
发帖数: 78 | 23 最后一题就是从目标出发走平地或者上坡能到达到的最高坐标BFS一遍就好了
anagram 那题就是把 abc -> (25)bc a(25)c ab(25) （25或者26 看相同词他要true还
是false）全放在hash里面 然后来一个查一次就行呗
投票题prorityQueue 扫描线法 如果要再快速统计当前时间的topk 建一个hashheap
图题求union BFS找一下
merge那题 不明白楼主说什么
btw 鄙人拙见 。。。 |
|
r*****s
发帖数: 1815 | 24 线段树扫描线分割成小矩形，然后用2
你的思路是对的
: 电面的时候给了几个想法
: 1. 给一个bounding box, 然后采用拒绝采样，如果很变态的形状会很变
态高 比
如十字
: 型交叉
: 2. 分割成若干个小的然后加入list
: 三哥面的，本来以为要跪了，最后phone screen还是给过, recruiter说
还给了
很高的
: score
: 为3
|
|
发帖数: 1 | 25 嗯呢，我也有道题卡了很久，看了保健的签名，突然懂了，原来是扫描线+线段树
[在 dabaojian (蔡宝健) 的大作中提到：] |
|
m*********y
发帖数: 1735 | 26 B Ultrasound
超声在医学上的应用有A超，B超，C超，M超，多普勒彩超
A超就是医学成像系统上所说的一条A line，就是超声从某个点打进去，然后描绘回波
和时间的关系曲线，就是一个点上在深度方向上的回波时间曲线，是一维曲线，称为A超
B超是在每扫描完一条A line之后很快的将超声探头沿某一直线移动，所以，就是探测
某一条线上在深度方向上的回波信号，所以是二维图像，称为B超。应用最为广泛，医
学上的超声大多是B超。
C超是为探测某一深度信息而设计。对每次超声回波信号，C超值是采集指定深度的信号
用于重建，所以需要不断移动扫描线并最终获得类似B超的二维图像。但C超只是某一个
断面的扫描信号，而B超是所有信号的投影叠加。
M超主要是用于动态监测心动周期内脏器的运动情况。其结果横坐标是时间，在每个时
间点上都是一条A line，相当于A超沿时间扩展。这样因为不同时间脏器位置不同，超
声回波信号强度等也不同，所以可以动态观察脏器的位置。
总体来说，A超，B超，M超都是一回事。A超是一条A line，B超是A line沿空间直线扩
展，M超是A line沿时间扩展。C超是某一断面上的 |
|
t*******r
发帖数: 22634 | 27 外加 lower bound 和 upper bound 两边夹击。。。
不过我觉得大多数人先保持总和 11 不变吧，题目有两个 constraint，
把两个 constraint 同时放宽的话，不是把一维空间扫描线问题，变成
两维空间里狂扫？这题目不需要同时放宽两个 constraint 才能解吧。。。 |
|
b**g
发帖数: 588 | 28 反转片效果，黑白效果，单色效果，加电视扫描线。一通乱忙活，齐活儿。为了100伪
币奔了。 |
|
w*******g
发帖数: 342 | 29 现在拍4k的video意义不大，因为基本上大众化的显示器和电视都还看不了。（市面上
的1080p相当于4k扫描线数量的一半，面积的1/4）。俺进了黑版hero3后就后悔了，还
不如买银版的省点银子。
你说降低到这个尺寸是指照片吗？照片可以越大越好，反正在屏幕上可以静态放大。视
频嘛，俺觉得1080就可以了，当然如果能拍到每秒60帧，截屏会清楚一些，而且还可以
放慢看。 |
|
e********g
发帖数: 2524 | 30 http://dashuyuan.spaces.live.com/blog/cns!7767F1EAB39CEEA4!460.entry
游戏机光线枪的工作原理（摘录）
编者按：
小时候就总玩游戏机（那时还是任天堂的红白机，怀念ing）的《打野鸭》、《
打飞碟》之类的射击游戏，也就是需要配个外设“光线枪”的那种。很久以来我一直挺
困惑这光线枪究竟是怎么个工作原理的？今天在网上偶然看到了这么一篇文章（原文）
，了却了我多年来的纳闷。现在摘录其中能说明问题的一段，大家玩游戏也要当个明白
人儿——
和我们想象的不同，光线枪不会射出光线，只能接收光线。在接收到光线后，光
线枪会把枪口对准点的信号传回给游戏机，对应的软件就会告诉主机枪口所瞄准的位置
在哪里。
那么软件又是怎么测量位置的呢？如果你仔细观察的话，当按下扳机后，无论枪
口是否对着屏幕，屏幕上总会有一道闪光，而这道由软件控制发出的白色帧就是光枪测
位的关键。
在此之前我们还有必要先来看一下隔行扫描电视机的成像方式：在PAL\NTSC的
CRT电视中，扫描线是影像生成的方式。以NTSC为例， |
|
L*****k
发帖数: 13042 | 31 1024是横向的像素数(列)
576是扫描线数(行)
720p是指HDTV能逐行扫描到720根水平线。
所以我说这玩意达不到720p |
|
s**********s
发帖数: 7387 | 32 问题是这里没人愿意去拍胶片来测吧。而且扫35mm胶片，特别是边角，可是非常讲究的
，9000ED那个杯具的玻璃片夹是没戏的，起码得液封的aztek片夹，或者imacon/滚扫之
类能够实现扫描线完美平直的系统。 |
|
m******s
发帖数: 204 | 33 请教一下这里面涉及到并行计算吗？另外，不太清楚和图形学有什么关系？我理解的三
维图形学两大分支：扫描线渲染和光线追踪。请赐教。
基本是一回事情。具体地说，就是考虑到三维空间里面的光都是一条线，每条线可以参
数化成一个点(3D)和一个方向(2D)。如果不考虑光在这条线上的衰减，那么可以继续简
化为一个4D(2D+2D)的光空间。这个空间就是Light field。
2D采样，所以可以随便换视角（只要在相机覆盖的范围内）。但Ng的work主要做的是怎
么在一个single view上拍不同focus length的照片，用来refocus。虽然也是采样，但
空间要小很多。所以他做出来的实际上是原来意义上的light field的一个小子集。在
小范围上动动视角有点3D效果在3D电视上应该没有问题，但大角度的显然handle不了。
compressive sensing，具体就不说了。他的paper一部分是关于硬件，一部分是关于用
wavelet的理论，时间太长，记不了那么多了。 |
|
v*******e
发帖数: 1715 | 34
haha .真是开玩笑.
下次看电影的时候,你能数出每一祯, 或者看电视的时候能看出扫描线,再来扯
10负2此方吧. 负32次方? 赫赫.
一“弹指”为7.2秒，一“瞬间”为0.36秒，一“刹那”却只有0.018秒
在《僧只律》中即有这样的记载：“一刹那为一念，二十念为一瞬，二十瞬为一弹指，
二十弹指为一罗预，二十罗预为一须臾，一日一夜有三十须臾。”据此，可推算出具体
时间来。即一天一夜24小时，有480万个“刹那”或24万个“瞬间”，1.2万个“弹指”
，30个“须臾”。再细算，一昼夜有8.64万秒，那么，一“须臾”等于2880秒，一“弹
指”为7.2秒，一“瞬间”为0.36秒，一“刹那”却只有0.018秒
10的负二次方,看明白还是可能的...在念头问题上,视觉上恐怕没希望了,至少很难.
还有说一弹指六十刹那，一刹那九百生灭,所以,10负4次方,几乎就是头了.
而这900,我认为是并发,而不是串行.如同说电影的每一祯(3刹那),
如果里面包含的物体超过900个,你就分辨不过来了....这个不肯定.
其他的就不评论了.
2分
扰能 |
|
a**u
发帖数: 8107 | 35 ☆─────────────────────────────────────☆
runsun02 (runsun) 于 (Sun Jan 10 19:57:30 2010, 北京) 提到:
老兄写了几篇自认为2000年来都无人能及的对禅定介绍的网文，看了后让我实在哭笑不
得。不过看你挺有劲头，那么在下就想问问你几个关于禅定的问题，请兄答一下。
1.某男在十分钟时间乃至更长时间内一直在看眼前的苹果，一丝一毫无间隙不偏离苹果
这个目标并导致忘身，请问某男在此时间段是否一定在禅定当中？
2.某男百分之一秒的时间内看眼前的苹果，一丝一毫无间隙不偏离苹果这个目标并导致
忘身，请问某男在此百分之一秒时间内是否一定在禅定当中？
3.某男一普朗克时间（10的负32次方秒）内看眼前的某物，一丝一毫无间隙不偏离该目
标，请问某男在此一普朗克时间内是否一定在禅定当中？
4.某男很喜欢看美女，紧紧盯住某美女不放，除了看美女之外无它念并导致忘身，时间
长达十分钟乃至更长，请问某男在此十分钟内是否一定在禅定当中？
5.某男极度愤怒，念念专注于杀了对方，除了杀了对方之念再无它念并导致忘身，时间
长达十分钟... 阅读全帖 |
|
r****y
发帖数: 26819 | 36 没有1080根水平扫描线，或者没有1080个垂直像素，也可称为1080p？ |
|
|
C*****N
发帖数: 318 | 38 我有一台acer travelmate6292. 屏幕被砸坏了，只好接到显示器上。但是效果不行，
可以看到扫描线。其他的本本接到这个显示器上正常。是不是我的acer什么地方坏了？
怎么才能解决？ |
|
h**t
发帖数: 1045 | 39 差不多吧.要扫描线扫到才消,越到后面,扫描得越慢,所以越难
一次消得越多,分数越高. |
|
